# UVA1416 Warfare And Logistics（最短路/树）

## Warfare And Logistics

The army of United Nations launched a new wave of air strikes on terroristforces. The objective of the mission is to reduce enemy's logistical mobility. Each airstrike will destroy a path and therefore increase the shipping cost of the shortest pathbetween two enemy locations. The maximal damage is always desirable.

Let's assume that there are n enemy locations connected by m bidirectional paths,each with specific shipping cost. Enemy's total shipping cost is given as $\sum_{i=1}^{n}\sum_{j=1}^{n}path(i, j)$. Here path(i, j) is the shortest path between locations i and j. In case i and j are not connected, path(i, j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is noted as c'. In order to maximizedthe damage to the enemy, UN's air force try to find the maximal c' - c.

### Input

The first line ofeach input case consists ofthree integers: n, m, and L. $1 < n <= 100,1 <= m <= 1000, 1 <= L <= 10^8$. Each ofthe following m lines contains three integers: a,b, s, indicating length of the path between a and b.

### Output

For each case, output the total shipping cost before the air strike and the maximaltotal shipping cost after the strike. Output them in one line separated by a space.

### Sample Input

4  6  1000
1  3  2
1  4  4
2  1  3
2  3  3
3  4  1
4  2  2

### Sample Output

28  38

### 链接

https://cn.vjudge.net/problem/UVA-1416

——小白书P330

### 代码

StatusAccepted
Time200ms
Length2557
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
const int maxm = 1010;
ll dist[maxn], ans[maxm];
bool vis[maxn];
int pre1[maxn], pre2[maxn];
int n, m, L;

struct Node
{
int v;
ll dis;
Node(int _v, ll _dis): v(_v), dis(_dis) {}
bool operator < (const Node & r) const
{
return dis > r.dis;
}
};

struct Edge
{
int to, id, cost;
Edge(int _to, int _cost, int _id): to(_to), cost(_cost), id(_id) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, int w, int id)
{
edge[u].push_back(Edge(v, w, id));
}

ll dijkstra(int s, int e)
{
for (int i = 0; i <= n; ++i)
{
dist[i] = inf;
pre1[i] = 0;
vis[i] = false;
}
dist[s] = 0;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int id = edge[u][i].id, v = edge[u][i].to;
if (id == e)
continue;
if (!vis[v] && dist[v] > dist[u] + edge[u][i].cost)
{
dist[v] = dist[u] + edge[u][i].cost;
pre1[v] = id; // 记录边的编号
Q.push(Node(v, dist[v]));
}
}
}
ll sum = 0;
for (int i = 1; i <= n; ++i) // 从s出发的所有最短路
{
if (dist[i] == inf)
sum += L;
else
sum += dist[i];
}
return sum;
}

void solve()
{
for (int i = 1; i <= n; ++i)
{
ll cost = dijkstra(i, 0);
for (int j = 0; j <= m; ++j) // 不删边时的最短路和
ans[j] += cost;
memcpy(pre2, pre1, sizeof(pre1)); // 将记录的最短路编号复制给pre2数组
for (int j = 1; j <= n; ++j)
{
if (pre2[j]) // 删除边pre2[j]后的最短路之和
ans[pre2[j]] += ((dijkstra(i, pre2[j])) - cost);
}
}
}

int main()
{
int u, v, w;
while (scanf("%d%d%d", &n, &m, &L) != EOF)
{
for (int i = 0; i <= n; ++i)
edge[i].clear();
for (int i = 0; i <= m; ++i)
ans[i] = 0;
for (int i = 1; i <= m; ++i) // 边的编号从1开始
{
scanf("%d%d%d", &u, &v, &w);
}