题目描述
参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。
同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。
他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。
jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。
输入输出格式
输入格式：
第一行两个整数N,M,N为城市数，M为道路数。
接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度。
输出格式：
一行，按递增次序输出若干的数，表示重要的城市。
如果没有点的话需要输出一行
“No important cities.”
去掉引号。
输入输出样例
输入样例#1：
4 4 1 2 1 2 3 1 4 1 2 4 3 2输出样例#1：
2说明
30%的数据：N≤20N≤20；
60%的数据：N≤100N≤100；
100%的数据：N≤200,M≤N×(N−1)2,0<c≤10000N≤200,M≤N×(N−1)2,0<c≤10000。cc即路的长度。
保证不出现重边和自环
感谢@赵昕鹏 和@qq2477259579 提供程序
*****************************************分割线*************************************************
一看数据范围，floyd没得跑。
在Floyd更新（松弛）的同时记录：
最后见答案记录在a数组中，去重（注意a数组范围200*200，否则会RE）。（血的教训）
粘代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int maxn=205; 8 int n,m; 9 struct node{ 10 int zhi,k; 11 }dis[maxn][maxn]; 12 void init() 13 { 14 scanf("%d%d",&n,&m); 15 memset(dis,0x3f,sizeof dis); 16 for(int i=1,a,b,c;i<=m;i++) 17 { 18 scanf("%d%d%d",&a,&b,&c); 19 dis[a][b].zhi=dis[b][a].zhi=c; 20 } 21 } 22 void floyd() 23 { 24 for(int k=1;k<=n;k++) 25 for(int i=1;i<=n;i++) 26 for(int j=1;j<=n;j++) 27 { 28 if(k==i) break; 29 if(k==j) continue; 30 if(i==j) continue; 31 int temp=dis[i][k].zhi+dis[k][j].zhi; 32 if(temp<dis[i][j].zhi) 33 { 34 dis[i][j].zhi=temp; 35 dis[i][j].k=k; 36 } 37 else if(temp==dis[i][j].zhi) 38 { 39 dis[i][j].k=0x3f3f3f3f; 40 } 41 } 42 } 43 int a[50009]; 44 int main() 45 { 46 init(); 47 floyd(); 48 int cnt=0; 49 for(int i=1;i<=n;i++) 50 for(int j=i+1;j<=n;j++) 51 { 52 if(dis[i][j].k!=0x3f3f3f3f) a[++cnt]=dis[i][j].k; 53 } 54 if(cnt==0) {cout<<"No important cities.";return 0;} 55 sort(a+1,a+1+cnt); 56 for(int i=1;i<=cnt;i++) 57 { 58 if(a[i]!=a[i-1]) cout<<a[i]<<" "; 59 } 60 }
原文：https://www.cnblogs.com/sdfzjdx/p/10493352.html