CF1204C Anna, Svyatoslav and Maps 题解
题目链接：CF1204C Anna, Svyatoslav and Maps
题意：
对于 \(n(n \le 100)\) 个点有向无环图，给出一个由 \(m(m \le 10^6)\) 个点组成的的路径 \(p\)（不保证是简单路径，但保证对于 \(1 \le i < m,p_i\) 与 \(p_{i+1}\) 之间有边）， 要求从 \(p\) 中选出一个最短的子序列 \(v\)（假设长度为 \(k\) ），满足 \(v_1=p_1,v_k=p_m\) ，并且 \(p\) 是按顺序经过 \(v\) 的最短路径之一。
输入格式:
The first line contains a single integer \(n\) ( \(2 \le n \le 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 \le m \le 10^6\) ) — the number of vertexes in the path.
The next line contains \(m\) integers \(p_1, p_2, \ldots, p_m\) ( \(1 \le p_i \le n\) ) — the sequence of vertexes in the path. It is guaranteed that for any \(1 \leq i < m\) there is an arc from \(p_i\) to \(p_{i+1}\) .
输出格式：
In the first line output a single integer \(k\) ( \(2 \leq k \leq m\) ) — the length of the shortest good subsequence. In the second line output \(k\) integers \(v_1,\ldots,v_k\) ( \(1 \leq v_i \leq n\) ) — the vertexes in the subsequence. If there are multiple shortest subsequences, print any. Any two consecutive numbers should be distinct.
题目的意思有点鬼畜，其实就是问你这个最短路径构成的路线中有多少个点是可以删掉的。
注意到如果 \(d(i,j) > d(i,k) + d(k,j)\) ，则点 \(k\) 就不能删除。
也就是说在 \(i,j\) 最短路径上的非 \(i,j\) 点可以删除。
注意到 \(n\) 非常小，所以我们可以用 \(\mathtt{Floyd}\) 预处理一下最短路，然后扫一遍就好了。
时间复杂度 \(\mathcal{O}(n^3 + |p|)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(115))
#define M ((int)(1e6+14))
char s[N],vis[N];
int n,m,g[N][N],d[N][N],p[M];
vector<int> vec;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> (s+1);
for(int j=1; j<=n; j++)
{
d[i][j] = g[i][j] = s[j] - '0';
if(d[i][j] == 0) d[i][j] = INF;
if(i == j) d[i][j] = 0;
}
}
cin >> m;
for(int i=1; i<=m; i++) cin >> p[i];
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) down(d[i][j], d[i][k] + d[k][j]);
vec.push_back(p[1]);
int lst = p[1], cur = 0;
for(int i=2; i<=m; i++)
{
cur += d[p[i-1]][p[i]];
if(d[lst][p[i]] < cur)
{ lst = p[i-1]; vec.push_back(lst); cur = d[lst][p[i]]; }
}
vec.push_back(p[m]); cout << vec.size() << '\n';
for(int i=0; i<vec.size(); i++) cout << vec[i] << " \n"[i==vec.size()-1];
return 0;
}参考文献：
