CF1204C题解

· · 题解

思路

首先，考虑什么时候 j 能成为 i,k 间最短路的必经点，必经点的定义为存在一条 i 到 k 的最短路径经过 j。显然应当满足 dis_{i,k}=dis_{i,j}+dis_{j,k}，j 才能成为必经点。接下来有一个结论，如果 j 是 i,k 的必经点，k 是 i,p 的必经点，则 j,k 一定都是 i,p 的必经点。为什么呢？因为 dis_{i,k}=dis_{i,j}+dis_{j,k}，dis_{i,p}=dis_{i,k}+dis_{k,p}，则有 dis_{i,p}=dis_{i,j}+dis_{j,k}+dis_{k,p}，这满足最短路的定义。所以该结论成立。

因此先跑一遍最短路，然后用两个指针不断按照上述结论判断即可。具体实现可参考代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
const int M=1e6+5;
int n,a[N][N],f[N][N],m,c[M],d[M],cnt;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
signed main(){
    freopen("std.in","r",stdin);
    memset(f,0x3f,sizeof(f));
    n=read();
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        for(int j=1;j<=n;j++){
            a[i][j]=s[j-1]-'0';
            if(a[i][j])f[i][j]=a[i][j];
        }
    }
    m=read();
    for(int i=1;i<=m;i++)c[i]=read();
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    int lst=1;d[++cnt]=c[1];
    for(int i=2;i<=m;i++){
        //cout<<c[lst]<<" "<<c[i]<<" "<<c[i+1]<<" "<<f[c[lst]][c[i+1]]<<" "<<f[c[lst]][c[i]]<<" "<<f[c[i]][c[i+1]]<<endl;
        if(f[c[lst]][c[i+1]]==f[c[lst]][c[i]]+f[c[i]][c[i+1]]&&c[lst]!=c[i+1]){

        }
        else{
            d[++cnt]=c[i];lst=i;
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)cout<<d[i]<<" ";
    return 0;
}