题解：P10927 Sightseeing trip

· · 题解

洛谷什么时候把这题 SPJ 修一修啊……

LOJ AC 记录。

相信大家都做过 P6175 无向图的最小环问题。而那题是本题的严格弱化版。

什么？没做过？

我们简单回顾下，在那题的最高赞题解中提到：

在 Floyd 算法枚举 k 的时候，已经得到了前 k-1 个点中每两个点的最短路径，这 k-1 个点不包括点 k，并且他们的最短路径中也不包括 k 点。

那么我们便可以从这前 k-1 个点中选出两个点 (i,j) 来，因为 dis_{i,j} 已经是此时 (i,j) 间的最短路径，且这个路径不包含 k 点。

所以连接 i\to j\to k\to i ，我们就得到了一个经过 (i,j,k) 的最小环。

容易发现，本题只需要稍微推导可以转化为以上形式。唯一不同只在输出方案。

那么既然本题的难度升了两个颜色，输出方案想必很难吧！（其实按作者愚见，P6175 应该升绿……）

其实不难，只需要在每次更新最短路时把方案更新就行，记录方案的操作是很常规的，由于数据范围很小，所以不用担心超时。

首先 j\to k\to i 这部分是没变的，只需要把 i\to j 的部分更新掉就行了。具体的方法，就是记录 p 数组，p_{i,j}=k 代表上次 p_{i,j} 是从 dis_{i,k}+dis_{k,j} 转移来的，每次递归跳 (i,p_{i,j}) 和 (p_{i,j},j) 即可，而如果 p_{i,j}=0，说明 g_{i,j} 即为 (i,j) 最短路径，直接返回。

局部代码如下：

void check(int x,int y){
    if(!p[x][y]) return;
    check(x,p[x][y]);
    path.push_back(p[x][y]);
    check(p[x][y],y);
}
......
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long)dis[i][j]+g[i][k]+g[k][j]<ans){
                    ans=dis[i][j]+g[i][k]+g[k][j];
                    path.clear();
                    path.push_back(i);
                    check(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    p[i][j]=k;
                }
            }
        }

完整代码如下：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,u,v,d,dis[101][101],g[101][101],p[101][101],ans=0x3f3f3f3f;
vector<int>path;
void check(int x,int y){
    if(!p[x][y]) return;
    check(x,p[x][y]);
    path.push_back(p[x][y]);
    check(p[x][y],y);
}
int main(){
    cin>>n>>m;
    memset(dis,0x3f,sizeof dis);
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++){
        dis[i][i]=0;
        g[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v>>d;
        dis[u][v]=min(dis[u][v],d);
        dis[v][u]=min(dis[v][u],d);
        g[u][v]=min(g[u][v],d);
        g[v][u]=min(g[v][u],d);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long)dis[i][j]+g[i][k]+g[k][j]<ans){
                    ans=dis[i][j]+g[i][k]+g[k][j];
                    path.clear();
                    path.push_back(i);
                    check(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    p[i][j]=k;
                }
            }
        }
    }
    if(ans==0x3f3f3f3f) cout<<"No solution.";
    else for(int i=0;i<path.size();i++) cout<<path[i]<<" ";
}