解题：JSOI 2007 重要的城市

时间：2022-05-19 21:33:22

题面

考虑一个点$x$，如果某两个点$u,v$间的所有最短路都经过$x$，那么$x$肯定是重要的。这个题$n$比较小，所以我们直接跑floyd，在过程中记录

当发生松弛时，我们具体讨论：

如果这个长度是两点间新更新出的一条最短路，即$dis[i][j]>dis[i][k]+dis[k][j]$，我们在$i,j$的路径上记录$k$这个点

如果这是一条长度在以前更新过的最短路，那么说明两点间不只有一条最短路，原来的那个点已经废了，更新一下

 #include<set>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int mat[N][N],imp[N][N];

 int n,m,t1,t2,t3;

 set<int> ss;

 int main ()

 {

     scanf("%d%d",&n,&m);

     memset(mat,0x3f,sizeof mat);

     for(int i=;i<=n;i++) mat[i][i]=;

     for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&t1,&t2,&t3);

         mat[t1][t2]=mat[t2][t1]=t3;

     }

     for(int k=;k<=n;k++)

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 if(i!=j&&i!=k&&j!=k)

                 {

                     if(mat[i][j]>mat[i][k]+mat[k][j])

                         mat[i][j]=mat[i][k]+mat[k][j],imp[i][j]=k;

                     else if(mat[i][j]==mat[i][k]+mat[k][j])

                         imp[i][j]=;

                 }

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             if(imp[i][j]) ss.insert(imp[i][j]);

     if(ss.empty()) printf("No important cities.");

     while(!ss.empty())

         printf("%d ",*ss.begin()),ss.erase(ss.begin());

     return ;

 }

相关文章