5. 【NOIP2016】交通中断

有一个小国家，国家内有n座城市和m条双向的道路，每条道路连接着两座不同的城市。其中1号城市为国家的首都。由地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有i(i＞1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第i个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。 对于每一个城市i，假定只有第i个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。 我们采用邻接表的方式存储图的信息，其中head[x]表示顶点x的第一条边的编号，next[i]表示第l条边的下一条边的编号，point[i]表示第1条边的终点，weight[i]表示第l条边的长度。

#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define INF 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] = INF;
    ① ;
    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 (②) {
                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];
        }
        ③ ;
        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 && ④ && visit[point[j]] == 0) {
                    ⑤ ;
                    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
• next[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[next[j]] = 0
• visit[queue[t]] = 1
• visit[point[j]] = 1