题解 CF1204C 【Anna, Svyatoslav and Maps】

发表于 更新于 阅读次数： Waline：
CF1204C 【Anna, Svyatoslav and Maps】题解。

这个题其实还是挺简单的，但我还是想了很久而且还被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]必须要去一次。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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<<' ';//输出
}