题解 CF1204C 【Anna, Svyatoslav and Maps】

CHU2 · 2019-08-21 23:13:00 · 题解

大家的做法都踩爆我的做法啊QAQ

Floyd先预处理出最短路。然后设f[i]表示dp到位置i时最短的序列长度。j(j<i)能转移到i当且仅当dis[a[j]][a[i]]==i-j

又注意到最短路长度最长为n，于是就得到了一个跑得巨慢无比但能通过本题的做法。时间复杂度O(nm)

代码：

#include <bits/stdc++.h>
#define N 105
#define M 1000005
#define For(i,x,y) for(register int i=(x);i<=(y);++i)
#define Rof(i,x,y) for(int i=(x);i>=(y);--i)
using namespace std;
int a[M],g[N][N],f[M],trans[M],ans[M];
char s[N];
inline void rd(int &x){
    int y=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0' && c<='9') y=y*10+c-'0',c=getchar();
    x=y;
}
int main(){
    int n,m,cnt=0;scanf("%d",&n);
    memset(g,0x3f,sizeof(g));
    memset(f,0x3f,sizeof(f));
    For(i,1,n){
        scanf("\n%s",s+1);
        For(j,1,n)
            if(s[j]=='1') g[i][j]=1;
    }
    rd(m);
    For(i,1,m) rd(a[i]);
    For(k,1,n) For(i,1,n) For(j,1,n) g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
    For(i,1,n) g[i][i]=0;
    f[1]=1;
    For(i,1,m)
        For(j,max(i-n,1),i-1)
            if(i-j==g[a[j]][a[i]] && f[i]>f[j]+1) f[i]=f[j]+1,trans[i]=j;
    printf("%d\n",f[m]);
    for(register int i=m;i;i=trans[i]) ans[++cnt]=a[i];
    Rof(i,cnt,1) printf("%d ",ans[i]); 
}