Codeforces 581 Div2 C

图片说明

题意：
题意是给出一个有向图，每条边的距离都是1，然后给出一个序列，即一条路径，输出一个该序列最小的子序列，且要求该子序列可以还原成原序列，差不多这个意思，读题读自闭了。
题解：
首先跑一边floyd，算出每个节点的最短路径，注意初始化。
遍历序列，当n>3的时候，如果a[x][y] + a[y][k] == a[x][k]，那么就可以将中间的点给去掉，不影响走的路。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 1e9+7;
int a[110][110];
int ans[1000010];
int n,m,k,cnt = 0;
char c;
int main()
{
    memset(a,inf,sizeof(a));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        a[i][i] = 0;
        for(int j=1;j<=n;j++)
        {
            cin>>c;
            if(c == '1')
                a[i][j] = 1;
        }
    }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j] = min(a[i][j],a[i][k]+a[k][j]);

    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        if(i <= 2){
            ans[++cnt] = k;
        }
        else{
            int x = ans[cnt-1];
            int y = ans[cnt];
            if(a[x][y] + a[y][k] == a[x][k]){
                ans[cnt] = k;
            }else{
                ans[++cnt] = k;
            }
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}