CF1204C Anna, Svyatoslav and Maps 题解
Otomachi_Una_
·
·
题解
题目简述
- 给你一个 DAG 上面的一条路径 \{p_m\}。
- 求 p 上面包含 p_1,p_m 的最短点列 v。
-
-
解题思路
那也就是说我们要一个个去查，假设当前加入 $v$ 序列的队尾是 $v'(=p_x)$。那么当 $dis(v',p_i)\not = i-x$ 时必须选上 $p_{i-1}$。模拟即可。
## 参考代码
```cpp
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
const int MAXN=1e2+5;
const int MR=1e6+5;
int dis[MAXN][MAXN];int n;
int p[MR];int m;
vector<int> v;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%1d",&dis[i][j]);
if(!dis[i][j])
dis[i][j]=1e9;
}
dis[i][i]=0;
}
cin>>m;
for(int i=1;i<=m;i++)
cin>>p[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
v.push_back(p[1]);int lst=1;
for(int i=2;i<=m+1;i++){
if(dis[p[lst]][p[i]]!=i-lst)
v.push_back(p[i-1]),lst=i-1;
}
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
```