yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

题解 CF1204C 【Anna, Svyatoslav and Maps】

posted on 2019-08-21 16:43:38 | under 题解 |

这个题其实还是挺简单的,但我还是想了很久而且还被hack了一次

思路:floyd+two-pointer+贪心

先floyd预处理出所有点之间的最短路,然后对于每个i找最靠后的j,满足 $dis[p[i]][p[j+1]]>=dis[i][j]+1$ ,即由p[i]到p[j+1]的最短路必过p[j]

然后把退出循环的p[j]塞进答案数组,因为这个p[j]必须要去一次。

代码:


#include <bits/stdc++.h>
using namespace std;
int n,m,p[1000005],a[105][105];
char x;
vector<int> ans;
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)a[i][j]=1926817;//初始化
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++){
        cin>>x;
        if(x=='1')a[i][j]=1;//读入图
    }
    for (int i=1;i<=n;i++)a[i][i]=0;
    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]);//Floyd求最短路
    cin>>m;
    for (int i=1;i<=m;i++)cin>>p[i];
    int i=1,j=2;ans.push_back(p[1]);//p[1]是必到的
    for (;i<=m&&j<=m;){
        while(j<m&&a[p[i]][p[j+1]]>=a[p[i]][p[j]]+1)j++;//j<m保证了下标不越界,我们要找能满足p[i]到p[j+1]的最短路必过p[j]的最后一个j
        ans.push_back(p[i=j++]);//p[j]要停一次,不然的话可能下一次最短路不过p[j]
    }
    cout<<ans.size()<<endl;
    for (vector<int>::iterator it=ans.begin();it!=ans.end();it++)cout<<*it<<' ';//输出
}