自动搬运

查看原文

来自洛谷，原作者为

	Parabola mua~mua~嘟嘟你的嘴

搬运于2025-08-24 21:30:56，当前版本为作者最后更新于2018-01-28 13:37:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不得不说

如果我在考场上遇到这题

只能拿50分

一开始做这题的时候

哈哈哈哈哈我不在js省且07年我才两岁

什么也没想，看200的数据范围我就直接暴力（连复杂度都没算）

于是思路就是模拟

先用Floyd跑一遍所有点都没被炸掉的最短路

然后在把每一个点都炸一遍

例如炸点x

那么我再跑一遍Floyd

如果中转点遇到x

那么我就continue

再把跑完的最短路和一开始跑的最短路比较

如果当中dis[i][j]>炸点x后的dis[i][j]

那么x就是重要的城市

那么时间复杂度就是每个点都跑一个Floyd为n^4

所以代码大致是下面这样

有注释

      #include<iostream>
      #include<cstdio>
      #include<algorithm>
      #include<queue>
      using namespace std;
      const int INF=2e6;
      int e[205][205],dis[205][205],m,n;//e邻接矩阵存边，dis[i][j]存i到j的最短路
      priority_queue<int> q;//输出最短路时要排序
      //从主程序开始阅读
      bool check(int x)
      {
          int map[205][205];//当炸掉点x时全图最短路
          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)//如果中转点为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;//如果炸掉点x后的最短路比原最短路大，证明x是重要的城市
                  }
          return false;//x不是重要的城市
      }
      int main()
      {
          cin>>n>>m;//读入边数m，点数n
          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]);//跑一遍Floyd

          for(int i=1;i<=n;i++)
          {
              if(check(i))//检测它是不是重要城市，这个时候把目光转向check函数
                  q.push(-i);//懒得将q改成从小到大，直接推负数进去
          }
          if(q.empty())   cout<<"No important cities.";//队空代表无重要城市   
          else
          {
              while(!q.empty())
              {
                  int v=-q.top();q.pop();
                  cout<<v<<' ';
              }
          }//输出
          return 0;
      }

这个时候

这段代码只能过5个点

开了氧气黑科技可以过七个点

那么我们要换一种思路

（我也是想了一个晚上）

设cnt[i][j]表示i到j的最短路径条数

如果点x在i到j的最短路中出现了cnt[i][j]次

即i到j的最短路中每一条都要经过x的话

那么x一定为重要城市

OK

总结一下上面

除了任意两点之间的最短路之外

我们还需要cnt[i][j]和i到j的每一条最短路所经过的点

但是

这很难实现

其实是我不会

思考一下

第一点

在松弛中

i到j的路径中

如果通过点k可以使路径长度缩小

那么

i到j的最短路一定要经过k

第二点

如果松弛中发现e[i][j]==e[i][k]+e[k][j]

那么一定会不止一条最短路

这个时候我们以前发现经过的点都不一定走

所以

题目的思路就变成了这样

在松弛中

if(e[i][j]>e[i][k]+e[k][j])
{
    e[i][j]=e[i][k]+e[k][j];                        city[i][j]=k;//k是重要城市
}

如果发现i到j不止一条最短路

那么从city[i][j]中移除点k

最后我们还有两步

一是题目要求的排序

二是我们算法的判重

那么两者综合

我们选用桶排序

定义一个bool形的数组

循环i至n和j至n

ans[city[i][j]]=true;

输出时

if(ans[i])

cout<<i;

所以整道题的思路就是这样了

代码我就不打注释了

觉得我写的好记得给个赞哦~

下为代码

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int INF=2e6;
    int e[205][205],city[205][205],m,n;
    bool ans[205],cs;
    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]=INF;
        for(int i=1,x,y,u;i<=m;i++)
        {
            cin>>x>>y>>u;
            e[x][y]=e[y][x]=u;
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                if(i!=k)
                    for(int j=1;j<=n;j++)
                        if(i!=j&&j!=k)
                        {
                            if(e[i][j]>e[i][k]+e[k][j])
                            {
                                e[i][j]=e[i][k]+e[k][j];
                                city[i][j]=k;
                            }
                            else if(e[i][j]==e[i][k]+e[k][j])
                                city[i][j]=-1;
                        }
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++)
                if(city[i][j]!=-1)
                    ans[city[i][j]]=true;    
        for(int i=1;i<=n;i++)
            if(ans[i])
                cout<<i<<' ',cs=true;
        if(!cs)
            cout<<"No important cities.";
        return 0;
    }