Problem - C - Codeforces

给你一个有n个顶点的无权图，以及由m个顶点的序列p1,p2,...,pm给出的路径（该路径不一定简单）；对于每个1≤i<m，有一个弧从pi到pi+1。

如果v是p的子序列，v1=p1，vk=pm，并且p是按顺序通过v1，...，vk的最短路径之一，则定义k顶点的序列v1，v2，...，vk为好。

如果一个序列a可以通过删除几个（可能是零个或全部）元素从b中得到，那么这个序列a就是一个序列b的子序列。很明显，序列p是好的，但你的任务是找到最短的好子序列。

如果有多个最短的好子序列，请输出其中任何一个。

输入
第一行包含一个整数n（2≤n≤100）--图形中顶点的数量。

接下来的n行通过邻接矩阵定义图形：如果有一个从顶点i到顶点j的弧，第i行的第j个字符就等于1，否则就等于0。

下一行包含一个整数m（2≤m≤106）--路径中顶点的数量。

下一行包含m个整数p1,p2,...,pm（1≤pi≤n）--路径中顶点的序列。保证任何1≤i<m的情况下，都有一个弧从pi到pi+1。

输出
在第一行输出一个整数k (2≤k≤m) - 最短好子序列的长度。在第二行输出k个整数v1, ..., vk (1≤vi≤n) - 子序列中的顶点。如果有多个最短子序列，则打印任何一个。任何两个连续的数字都应该是不同的。

例子
输入
4
0110
0010
0001
1000
4
1 2 3 4

输出
3
1 2 4

输入
4
0110
0010
1001
1000
20
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

输出
11
1 2 4 2 4 2 4 2 4 2 4

输入
3
011
101
110
7
1 2 3 1 3 2 1

输出
7
1 2 3 1 3 2 1

输入
4
0110
0001
0001
1000
3
1 2 4

输出
2
1 4
题解:
(先入为主,觉得点数很大,不知道咋记录任意两点距离,好久没写floyd,忘了往这方面想了(点数很小))

首先存边(记得i == j可能是1,但是存边要把其看作0)坑点

跑floyd记录任意两点间最短距离,

起点存入答案数组,从i = 2开始,记录目前距离res为0

如果答案数组的top到b[i]的距离 < b[i-1] 到b[i]的距离,说明中间走的不是最短路,把b[i-1]存进去,res 更改为d[b[i-1]][b[i]],否则res += d[b[i-1]][b[i]],最后别忘了把b[m]也存到答案数组

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
char s[104][104];
int d[104][104];
int b[1000050];
int ans[1000050];
void solve()
{int n;cin >> n;
//	memset(d,0x3f,sizeof d);for(int i = 1;i <= n;i++){cin >> s[i] + 1;for(int j = 1;j <= n;j++){if(s[i][j] == '1'){d[i][j] = 1;}else{d[i][j] = 1e9;}if(i == j)d[i][j] = 0;}}for(int k = 1;k <= n;k++){for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){d[i][j] = min(d[i][j],d[i][k] + d[k][j]);}}}int m;cin >> m;for(int i = 1;i <= m;i++){cin >> b[i];}int cnt = 0;ans[++cnt] = b[1];int res = 0;for(int i = 2;i <= m;i++){res += d[b[i - 1]][b[i]];if(d[ans[cnt]][b[i]] < res){ans[++cnt] = b[i - 1];res = d[b[i - 1]][b[i]];}}ans[++cnt] = b[m];cout << cnt <<"\n";for(int i = 1;i <= cnt;i++)cout <<ans[i] << " ";
}signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}