题意

在给定的序列P中求一个子序列,使得在图中按照该子序列进行最短路径移动时可以完整经过原序列P

code

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 105 #define maxm 1000010 #define inf 0x3f3f3f3f using namespace std ; int n ,m , idx ; char mp[maxn][maxn] ; int G[maxn][maxn] , point[maxm] , ans[maxm] ; int qu[maxm*2] ; int head = 1 , tail = 0 ; int main () { memset(G,0x3f,sizeof(G)) ; cin >> n ; for(int i = 1 ; i <= n ; i ++) { scanf("%s",mp[i]+1) ; } for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= n ; j ++) { if(mp[i][j] == '1') { G[i][j] = 1 ; } } G[i][i] = 1 ; } for(int k = 1 ; k <= n ; k ++) { for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= n ; j ++) { G[i][j] = min(G[i][j],G[i][k]+G[k][j]) ; } } } cin >> m ; for(int i = 1 ; i <= m ; i ++) { cin >> point[i] ; } int st = 1 , now = 2 ; while(now <= m) { int diss = now - st ; if(diss == G[point[st]][point[now]]) { if(head <= tail) { head ++ ; } qu[++tail] = now ; now ++ ; }else { ans[++idx] = point[st] ; if(head <= tail) { st = qu[head++] ; } } } ans[++idx] = point[st] ; if(ans[idx] != point[m]) { ans[++idx] = point[m] ; } cout << idx << endl ; for(int i = 1 ; i <= idx ; i ++) { cout << ans[i] << " " ; } return 0 ; }

溜了溜了