（交通中断）有一个小国家，国家内有 $n$ 座城市和 $m$ 条双向的道路，每条道路连接着两座不同的城市。其中 $1$ 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第 $i(i>1)$ 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 $i$ 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。

对于每一个城市 $i$，假定只有第 $i$ 个城市与外界交通中断，输出有多少个 城市会因此导致到首都的最短路径长度改变。

我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 $x$ 的第一条边的编号，next[i] 表示第 $i$ 条边的下一条边的编号，point[i] 表示第 $i$ 条边的终点，weight[i] 表示第 $i$ 条边的长度。（第一空 $2$ 分，其余 $3$ 分）

1#include <iostream>2#include <cstring>3using namespace std;4#define MAXN 60005#define MAXM 1000006#define infinity 21474836477int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];8int queue[MAXN], dist[MAXN], visit[MAXN];9int n, m, x, y, z, total = 0, answer;10void link(int x, int y, int z)11{12    total++;13    next[total] = head[x];14    head[x] = total;15    point[total] = y;16    weight[total] = z;17    total++;18    next[total] = head[y];19    head[y] = total;20    point[total] = x;21    weight[total] = z;22}23int main()24{25    int i, j, s, t;26    cin >> n >> m;27    for (i = 1; i <= m; i++)28    {29        cin >> x >> y >> z;30        link(x, y, z);31    }32    for (i = 1; i <= n; i++)33        dist[i] = infinity;34    (1);35    queue[1] = 1;36    visit[1] = 1;37    s = 1;38    t = 1;39    // 使用 SPFA 求出第一个点到其余各点的最短路长度40    while (s <= t)41    {42        x = queue[s % MAXN];43        j = head[x];44        while (j != 0)45        {46            if ((2))47            {48                dist[point[j]] = dist[x] + weight[j];49                if (visit[point[j]] == 0)50                {51                    t++;52                    queue[t % MAXN] = point[j];53                    visit[point[j]] = 1;54                }55            }56            j = next[j];57        }58        (3);59        s++;60    }61    for (i = 2; i <= n; i++)62    {63        queue[1] = 1;64        memset(visit, 0, sizeof(visit));65        visit[1] = 1;66        s = 1;67        t = 1;68        while (s <= t)69        { // 判断最短路长度是否不变70            x = queue[s];71            j = head[x];72            while (j != 0)73            {74                if (point[j] != i && (4) && visit[point[j]] == 0)75                {76                    (5);77                    t++;78                    queue[t] = point[j];79                }80                j = next[j];81            }82            s++;83        }84        answer = 0;85        for (j = 1; j <= n; j++)86            answer += 1 - visit[j];87        cout << i << ":" << answer - 1 << endl;88    }89    return 0;90}