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;
}参考文献：
