（交通中断）有一个小国家，国家内有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;
  dist[1]=0 ;
 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[x]+weight[j]<dist[point[j]] ) {
    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];
  }
    visit[x]=0   ;
    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 &&  dist[x]+weight[j]==dist[point[j]]
      && visit[point[j]] == 0) {
          visit[point[j]]=1  ;
          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;
}