（交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。

由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第 i(i>1) 个城市因地震而导致交通中断时，

首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。

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

我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 

x 的第一条边的编号，next[i] 表示第 i 条边的下一条边的编号，point[i] 表示第 i 条边的终点，weight[i] 表示第 i 条边的长度。（第一空 2 分，其余 

3 分）

#include <iostream>

#include <cstring>

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;

}