当前没有测试数据。

28．（完善程序）

（交通中断）有一个小国家，国家内有 $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;
  ____________________;
  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;
}

①：{{ input(1) }}

②：{{ input(2) }}

③：{{ input(3) }}

④：{{ input(4) }}

⑤：{{ input(5) }}