(交通中断）有一个小国家，国家内有n座城市和m

(交通中断）有一个小国家，国家内有n座城市和m条双向的道路，每条道路连接着两座不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1)个城市因地震而

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

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

我们采用邻接表的方式存储图的信息，其中head[x]表示顶点x的第一条边的编号，next[i]表示第i条边的下一条边的编号，point[i]表示第i条边的终点，weight[i]表示第i条边的长度。（第一空2分，其余3分）

#include

#include

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) {

\ttotal ;

\tnext[total] = head[x];

\thead[x] = total;

\tpoint[total] = y;

\tweight[total] = z;

\ttotal ;

\tnext[total] = head[y];

\thead[y] = total;

\tpoint[total] = x;

\tweight[total] = z;

}

int main() {

\tint i, j, s, t;

\tcin >> n >> m;

\tfor (i = 1; i <= m; i ) {

\t\tcin >> x >> y >> z; link(x, y, z);

\t}

\tfor (i = 1; i <= n; i ) dist[i] = infinity;

(1) ;

\tqueue[1] = 1;

\tvisit[1] = 1;

\ts = 1;

\tt = 1;

\t// 使用 SPFA 求出第一个点到其余各点的最短路长度

\twhile (s <= t) {

\t\tx = queue[s % MAXN];

\t\tj = head[x];

\t\twhile (j != 0) {

\t\t\tif ( (2) ) {

\t\t\t\tdist[point[j]] = dist[x] weight[j];

\t\t\t\tif (visit[point[j]] == 0) {

\t\t\t\t\tt ;

\t\t\t\t\tqueue[t % MAXN] = point[j];

\t\t\t\t\tvisit[point[j]] = 1;

\t\t\t\t}

\t\t\t}

\t\t\tj = next[j];

\t\t}

\t (3) ;

\t\ts ;

\t}

\tfor (i = 2; i <= n; i ) {

\t\tqueue[1] = 1;

\t\tmemset(visit, 0, sizeof(visit));

\t\tvisit[1] = 1;

\t\ts = 1;

\t\tt = 1;

\t\twhile (s <= t) { // 判断最短路长度是否不变

\t\t\tx = queue[s];

\t\t\tj = head[x];

\t\t\twhile (j != 0) {

\t\t\t\tif (point[j] != i && (4)

\t\t\t\t&&visit[point[j]] == 0) {

\t\t\t\t (5) ;

\t\t\t\t\tt ;

\t\t\t\t\tqueue[t] = point[j];

\t\t\t\t}

\t\t\t\tj = next[j];

\t\t\t}

\t\t\ts ;

\t\t}

\t\tanswer = 0;

\t\tfor (j = 1; j <= n; j )

\t\t\tanswer = 1 - visit[j];

\t\tcout << i << ":" << answer - 1 << endl;

\t}return 0;

}