给定一个有向图,给定一条有向路径,求一条顶点最少的路径,使得给定的路径是它的最短路
folyd预处理出任意两点间的最短路,然后判断是否可以缩点
#include<bits/stdc++.h> using namespace std; #define int long long typedef long long ll; #define sc(x) scanf("%I64d",&(x)); #define rd(A) for(int i=0;i<N;i++) scanf("%I64d",&A[i]); #define P pair<ll,ll> #define se second #define fi first #define pb push_back #define inf 1e18 #define endl '\n' #define mem(A) memset(A,0,sizeof A); #define maxn 1000+10 #define maxm 1000000+10 string A[maxn]; ll N,T,a,b,M; ll B[maxm]; ll v[maxm]; ll dis[maxn][maxn]; void folyd(int n) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { dis[i][j]=inf; if(A[i][j-1]=='1')dis[i][j]=1; if(i==j)dis[i][j]=0; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { for(int k=1; k<=n; k++) { dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); } } } } signed main() { sc(N); for(int i=1; i<=N; i++) { cin>>A[i]; } sc(M); folyd(N); for(int i=0; i<M; i++) { sc(B[i]); } int k=1; v[0]=B[0]; v[1]=B[1]; int pre=B[0]; int p=B[1]; for(int i=2; i<M; i++) { //cout<<k<<' '<<i<<endl; if(k>0&&dis[pre][B[i]]>dis[pre][p]) { //cout<<pre<<" "<<p<<" "<<i<<" "<<B[i]<<dis[pre][B[i]]<<' '<<dis[pre][p]<<endl; k--; pre=v[k-1]; p=v[k]; } //if(dis[pre][B[i]]<=dis[pre][p]) { v[++k]=B[i]; pre=v[k-1]; p=v[k]; } } cout<<k+1<<'\n'; for(int i=0; i<=k; i++) { cout<<v[i]<<' '; } }