2014
01-26

# Travel

One day, Tom traveled to a country named BGM. BGM is a small country, but there are N (N <= 100) towns in it. Each town products one kind of food, the food will be transported to all the towns. In addition, the trucks will always take the shortest way. There are M (M <= 3000) two-way roads connecting the towns, and the length of the road is 1.
Let SUM be the total distance of the shortest paths between all pairs of the towns. Please write a program to calculate the new SUM after one of the M roads is destroyed.

The input contains several test cases.
The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
The input will be terminated by EOF.

The input contains several test cases.
The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
The input will be terminated by EOF.

5 4
5 1
1 3
3 2
5 4
2 2
1 2
1 2

INF
INF
INF
INF
2
2

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define N 105
#define M 6001

struct EDGE {
short b, next, id;
};
int G[N], sum[N], tot;
EDGE ET[M];
bool vv[N][M];
void addedge(int a, int b, int id) {
EDGE x = { b, G[a], id };
ET[tot] = x;
G[a] = tot++;
}

void init() {
tot = 0;
memset(G, -1, sizeof(G));
}

int n, m;
void bfs(int s) {
queue<int> Q;
bool v[N];
int x, rp, np, d = 0, i, j;
memset(v, 0, sizeof(v));
memset(vv[s], 0, sizeof(vv[s]));
Q.push(s), v[s] = 1, rp = 1,sum[s] = 0;
while (!Q.empty()) {
np = 0;
while (rp–) {
x = Q.front();
Q.pop();
sum[s] += d;
for (j = G[x]; j != -1; j = ET[j].next) {
i = ET[j].b;
if (!v[i]) {
Q.push(i);
v[i] = 1, vv[s][ET[j].id] = 1, np++;
}
}
}
rp = np, d++;
}
}

int bfs2(int s, int del) {
queue<int> Q;
bool v[N];
int x, rp, np, d = 0, i, j, ans = 0, cnt = 1;
memset(v, 0, sizeof(v));
Q.push(s), v[s] = 1, rp = 1;
while (!Q.empty()) {
np = 0;
while (rp–) {
x = Q.front();
Q.pop();
ans += d;
for (j = G[x]; j != -1; j = ET[j].next) {
if (ET[j].id == del) continue;
i = ET[j].b;
if (!v[i]) {
Q.push(i);
v[i] = 1, np++, cnt++;
}
}

}
rp = np, d++;
}
if (cnt != n) return -1;
return ans;
}

void solve() {
int i, j, a, b;
init();
for (i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
}
for (i = 1; i <= n; i++)
bfs(i);
for (i = 0; i < 2 * m; i += 2) {
int del = i / 2, ans = 0, t;
for (j = 1; j <= n; j++) {
if (vv[j][del] == 0) ans += sum[j];
else {
t = bfs2(j, del);
if (t == -1) {
ans = -1;
break;
}
ans += t;
}
}
if (ans == -1) printf("INF\n");
else printf("%d\n", ans);
}
}
int main() {
while (~scanf("%d%d", &n, &m))
solve();
return 0;
}

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的