(交通中断)有一个小国家,国家内有 n 座城市和 m 条双向的道路,每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道,如果只有第 i(i>1)个城市因地震而导致交通中断时,首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城 市,也认为到达该城市的最短路径长度改变。 对于每一个城市 i,假定只有第 i 个城市与外界交通中断,输出有多少个 城市会因此导致到首都的最短路径长度改变。 我们采用邻接表的方式存储图的信息,其中 head[x]表示顶点 x 的第一条 边的编号,next[i]表示第 i 条边的下一条边的编号,point[i]表示第 i 条边的终点, weight[i]表示第 i 条边的长度。(第一空 2 分,其余 3 分) #include #include using namespace std; #define MAXN 6000 #define MAXM 100000 #define infinity 2147483647 int head[MAXN], next[MAXM], point[MAXM], weight[MAXM]; int queue[MAXN], dist[MAXN], visit[MAXN]; int n, m, x, y, z, total = 0, answer; void link(int x,int y,int z) { total++; next[total] = head[x]; head[x] = total; point[total] = y; weight[total] = z; total++; next[total] = head[y]; head[y] = total; point[total] = x; weight[total] = z; } int main() { int i, j, s, t; cin >> n >> m; for (i = 1; i <= m; i++) { cin >> x >> y >> z; link(x, y, z); } for (i = 1; i <= n; i++) dist[i] = infinity; (1) ; queue[1] = 1; visit[1] = 1; s = 1; t = 1; // 使用 SPFA 求出第一个点到其余各点的最短路长度 while (s <= t) { x = queue[s % MAXN]; j = head[x]; while (j != 0) { if ( (2) ) { dist[point[j]] = dist[x] + weight[j]; if (visit[point[j]] == 0) { t++; queue[t % MAXN] = point[j]; visit[point[j]] = 1; } } j = next[j]; } (3) ; s++; } for (i = 2; i <= n; i++) { queue[1] = 1; memset(visit, 0, sizeof(visit)); visit[1] = 1; s = 1; t = 1; while (s <= t) { // 判断最短路长度是否不变 x = queue[s]; j = head[x]; while (j != 0) { if (point[j] != i && (4) &&visit[point[j]] == 0) { (5) ; t++; queue[t] = point[j]; } j = next[j]; } s++; } answer = 0; for (j = 1; j <= n; j++) answer += 1 - visit[j]; cout << i << ":" << answer - 1 << endl; } return 0; }