（交通中断）

有一个小国家，国家内有 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;
}

1. ①处应填（ ）{{ select(1) }}

• dist[1]=1
• dist[n]=1
• dist[1]=-1
• dist[1]=0

2. ②处应填（ ）{{ select(2) }}

• dist[point[x]]+weight[j]<dist[x]
• dist[j]+weight[x]<dist[ point[x] ]
• dist[x]+weight[j]<dist[ point[j] ]
• dist[x]+weight[ point[j] ]<dist[ j ]

3. ③处应填（ ）{{ select(3) }}

• t--
• visit[x]=0
• point[j]=j
• nxt[j]=point[j]

4. ④处应填（ ）{{ select(4) }}

• dist[x]+weight[j]==dist[ point[j] ]
• dist[x]+weight[ point[j] ]==dist[ point[j] ]
• dist[x]+weight[ point[j] ]==dist[ point[x] ]
• dist[point[x]]+weight[ point[j] ]==dist[point[j]]

5. ⑤处应填（ ）{{ select(5) }}

• visit[ point[j] ]=0
• visit[ nxt[j] ]=0
• visit[queue[t]]=1
• visit[point[j]]=1