【题解】codeforce1204 C. Anna, Svyatoslav and Maps⭐⭐⭐ 【Floyd】

codeforce1204 C. Anna, Svyatoslav and Maps⭐⭐⭐

The main characters have been omitted to be short.

You are given a directed unweighted graph without loops with n vertexes and a path in it (that path is not necessary simple) given by a sequence p1,p2,…,pm of m vertexes; for each 1≤i<m there is an arc from pi to pi+1.

Define the sequence v1,v2,…,vk of k vertexes as good, if v is a subsequence of p, v1=p1, vk=pm, and p is one of the shortest paths passing through the vertexes v1, …, vk in that order.

A sequence a is a subsequence of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements. It is obvious that the sequence p is good but your task is to find the shortest good subsequence.

If there are multiple shortest good subsequences, output any of them.

Input

The first line contains a single integer n (2≤n≤100) — the number of vertexes in a graph.

The next n lines define the graph by an adjacency matrix: the j-th character in the i-st line is equal to 1 if there is an arc from vertex i to the vertex j else it is equal to 0. It is guaranteed that the graph doesn’t contain loops.

The next line contains a single integer m (2≤m≤106) — the number of vertexes in the path.

The next line contains m integers p1,p2,…,pm (1≤pi≤n) — the sequence of vertexes in the path. It is guaranteed that for any 1≤i<m there is an arc from pi to pi+1.

Output

In the first line output a single integer k (2≤k≤m) — the length of the shortest good subsequence. In the second line output k integers v1, …, vk (1≤vi≤n) — the vertexes in the subsequence. If there are multiple shortest subsequences, print any. Any two consecutive numbers should be distinct.

Examples

inputCopy
4
0110
0010
0001
1000
4
1 2 3 4
outputCopy
3
1 2 4
inputCopy
4
0110
0010
1001
1000
20
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
outputCopy
11
1 2 4 2 4 2 4 2 4 2 4
inputCopy
3
011
101
110
7
1 2 3 1 3 2 1
outputCopy
7
1 2 3 1 3 2 1
inputCopy
4
0110
0001
0001
1000
3
1 2 4
outputCopy
2
1 4

Hint

题意:

不太好描述, 就是从当前最短路径里面删点, 删完后仍然能求得唯一的起点到终点的原路径, 建议仔细读一读样例就明白了了

题解:

对于一个点, 我们只在删去该点会出现"歧义"的情况下删掉该点. 有歧义的情况即为p[i]有更短的路径到p[i+1]
设初始权值为1, Floyd求一下多源最短路
dis为上一个点的累计距离, 即原序列距离, 在dis > G[ans[cnt]][p[i]]时添加该点
别忘了添加终点起点

经验小结:

#include<bits/stdc++.h>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<20;
const int maxn = 110;

int n, m, G[maxn][maxn];
int ans[maxn*maxn*maxn], p[maxn*maxn*maxn], cnt;
void Floyd(){
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            if(i != k)
                for(int j = 1; j <= n; ++j)
                    if(i != j && j != k)
                        G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
}
int main() {
    char c;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j){
            cin >> c;
            if(c == '1') G[i][j] = 1;
            else G[i][j] = inf;
            if(i == j) G[i][j] = 0;
        }
    cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> p[i];
    Floyd();
    ans[++cnt] = p[1];
    int dis = 0;
    for(int i = 2; i <= m; ++i){
        dis += G[p[i-1]][p[i]];
        if(dis > G[ans[cnt]][p[i]]){
            ans[++cnt] = p[i-1];
            dis = G[ans[cnt]][p[i]];
        }
    }
    ans[++cnt] = p[m];
    cout << cnt << endl;
    for(int i = 1; i <= cnt; ++i)
        cout << ans[i] << ' ';
    cout << endl;

    return 0;
}