题面
考虑一个点$x$，如果某两个点$u,v$间的所有最短路都经过$x$，那么$x$肯定是重要的。这个题$n$比较小，所以我们直接跑floyd，在过程中记录
当发生松弛时，我们具体讨论：
如果这个长度是两点间新更新出的一条最短路，即$dis[i][j]>dis[i][k]+dis[k][j]$，我们在$i,j$的路径上记录$k$这个点
如果这是一条长度在以前更新过的最短路，那么说明两点间不只有一条最短路，原来的那个点已经废了，更新一下
1 #include<set> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=205; 7 int mat[N][N],imp[N][N]; 8 int n,m,t1,t2,t3; 9 set<int> ss;10 int main ()11 {12 ????scanf("%d%d",&n,&m);13 ????memset(mat,0x3f,sizeof mat);14 ????for(int i=1;i<=n;i++) mat[i][i]=0;15 ????for(int i=1;i<=m;i++)16 ????{17 ????????scanf("%d%d%d",&t1,&t2,&t3);18 ????????mat[t1][t2]=mat[t2][t1]=t3;19 ????}20 ????for(int k=1;k<=n;k++)21 ????????for(int i=1;i<=n;i++)22 ????????????for(int j=1;j<=n;j++)23 ????????????????if(i!=j&&i!=k&&j!=k)24 ????????????????{25 ????????????????????if(mat[i][j]>mat[i][k]+mat[k][j])26 ????????????????????????mat[i][j]=mat[i][k]+mat[k][j],imp[i][j]=k;27 ????????????????????else if(mat[i][j]==mat[i][k]+mat[k][j])28 ????????????????????????imp[i][j]=0;29 ????????????????}30 ????for(int i=1;i<=n;i++)31 ????????for(int j=1;j<=n;j++)32 ????????????if(imp[i][j]) ss.insert(imp[i][j]);33 ????if(ss.empty()) printf("No important cities.");34 ????while(!ss.empty())35 ????????printf("%d ",*ss.begin()),ss.erase(ss.begin());36 ????return 0;37 }解题：JSOI 2007 重要的城市
原文地址：https://www.cnblogs.com/ydnhaha/p/9781192.html