其实这题还有个名字，不知道你们知道吗？
这题叫小A的作业，是我们周模拟的时候的考试题。（做过的握手）
当时真的是想思路想到自闭QAQ。
题目描述
参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。
同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。
他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。
jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。
输入输出格式
输入格式：
第一行两个整数N,M,N为城市数，M为道路数
接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度
输出格式：
一行，按递增次序输出若干的数，表示重要的城市。
输入输出样例
2
说明
30%的数据：Nle 20N≤20；
60%的数据：Nle 100N≤100；
100%的数据：Nle 200,Mle frac{N imes (N-1)}{2},0<cle 10000N≤200,M≤2N×(N−1),0<c≤10000。c即路的长度。
保证不出现重边和自环
如果没有点的话需要输出一行
“No important cities.”
去掉引号
那么，其实基础的思路很好想啊。就是我们跑一遍FLoyd，然后依次炸掉每一个没被炸过的点，比如炸点a，那么我们就再跑一遍，如果遇到a点，就continue；
然后再跑一遍Floyd，此时的dis如果大于原来的dis，那么就是我们要找到点。然后再炸，再跑.....依次重复。
代码放送（感谢代码原主人，因为我没写这个写法，如有不满请联系我，我可以删除，谢谢）
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int INF=2e6; int e[205][205],dis[205][205],m,n; priority_queue<int> q; bool check(int x) { int map[205][205]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { map[i][j]=e[i][j]; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(k==x) continue; map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(map[i][j]>dis[i][j]) return true; } return false; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) e[i][j]=dis[i][j]=0; else e[i][j]=dis[i][j]=INF; } for(int i=1,x,y,u;i<=m;i++) { cin>>x>>y>>u; e[x][y]=e[y][x]=dis[x][y]=dis[y][x]=u; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;i++) { if(check(i)) q.push(-i);if(q.empty()) cout<<"No important cities."; else { while(!q.empty()) { int v=-q.top();q.pop(); cout<<v<<' '; } } return 0; }
这样的话，你以为你是在做普及吗？？ 纯模拟TLE进行中。。。。（当然上面这个代码也不是人家的最终版！！）
然而你也可以50分滚蛋啦（写的好看的话会有50分的）
但是我不得不说，当你想到这点的时候，建议你还是别看题解，好好想想怎么优化吧。（毕竟基本思路是对的啊）
然后我们继续说下去。
我们可以使用一个数组 cnt 去记录 i 到 j 的最短路的个数呀。（我只是为了好理解用的cnt，代码不一定哦~ 毕竟我不鼓励抄代码的）
只要有点x在 i 到 j 的最短路中出现了cnt[i][j]次，那这就是重要大的一个了啊。
所以到了最重要的地方了。
首先是，对于i 和 j 来说，他们的最短路在经过重要的点x时，dis值一定会缩小的。
然后是，如果发现dis[i][j]=dis[i][k]+dis[k][j]的话，明显就还有别的最短路啊。
那么我们就可以记录一下。（如下）
if(f[k][i]+f[k][j]<f[i][j]) { f[j][i]=f[i][j]=f[k][i]+f[k][j]; a[i][j]=a[j][i]=k; }
然后我们进行一下题目要求的排序和算法本身的去重就好了啊。
那么这不是显然的桶排？
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]!=0&&a[i][j]!=i&&a[i][j]!=j) bz[a[i][j]]=true;
bool flag=false;
for(int i=1;i<=n;i++)
if(bz[i]) {
printf("%d ",i);
flag=1;
}
if(!flag) printf("No important cities.
");
那么放上代码（当然不会是考试时写的那份，是之后美化过的！！）
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int N=205; const int INF=2147483647; int f[N][N],a[N][N]; bool bz[N]; int main() { //freopen("city.in","r",stdin); //freopen("city.out","w",stdout); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=INF; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(x==y) continue; if(f[x][y]>z) { f[x][y]=z; f[y][x]=z; } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(f[k][i]!=INF) { for(int j=1;j<=n;j++) if(i!=j&&f[k][j]!=INF) { if(f[k][i]+f[k][j]<f[i][j]) { f[j][i]=f[i][j]=f[k][i]+f[k][j]; a[i][j]=a[j][i]=k; } else if(f[k][i]+f[k][j]==f[i][j]) a[i][j]=0; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]!=0&&a[i][j]!=i&&a[i][j]!=j) bz[a[i][j]]=true; bool flag=false; for(int i=1;i<=n;i++) if(bz[i]) { printf("%d ",i); flag=1; } if(!flag) printf("No important cities. "); return 0; }
最后，衷心的提醒你们一句，小心毒瘤数据（毕竟我考试就凉到80分QAQ）
谢谢。