【Floyd】CF1204 Anna, Svyatoslav and Maps

梦里梦外; 2024-03-22 11:12 57阅读 0赞

**看错题意了一直看不懂题解浪费了好多时间...**

![89d9fb3a0aa3436d85b758035ffeadea.png][]![8abf5d61438e40d099675d486197b608.png][]

思路：

先去考虑特殊的地方：

100

子序列

最短路径

一个个剖析：

100：考虑Floyd

子序列：DP?不懂

最短路径：考虑Floyd

我们要求的是子序列的方案，所以不大可能是DP

注意看它求的是什么，是按照子序列**这种顺序**跑，一定经过的是p这个路径

p这个路径保证是图中一个路径

换言之，是要删掉一些点，这些点满足：

一定在子序列的最短路径上

**所以我们要删掉的是在最短路上的点！**

那么考虑Floyd的松弛过程，当cur<dis时该点在最短路径上，所以删

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    int N,M;
    int dis[110][110],p[mxn];
    string s[110];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=N;j++){
    			if(i==j) dis[i][j]=0;
    			else dis[i][j]=1e18;
    		} 
    	}
    	for(int i=1;i<=N;i++) cin>>s[i],s[i]=" "+s[i];
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=N;j++){
    			if(s[i][j]=='1') dis[i][j]=1;
    		}
    	}
    	for(int k=1;k<=N;k++){
    		for(int i=1;i<=N;i++){
    			for(int j=1;j<=N;j++){
    				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    			}
    		}
    	}
    	cin>>M;
    	for(int i=1;i<=M;i++) cin>>p[i];
    	vector<int> v;
    	v.push_back(p[1]);
    	int last=p[1],cur=0;
    	for(int i=2;i<=M;i++){
    		cur+=dis[p[i-1]][p[i]];
    		if(cur>dis[last][p[i]]){
    			last=p[i-1];
    			v.push_back(last);
    			cur=dis[last][p[i]];
    		}
    	}
    	v.push_back(p[M]);
    	cout<<v.size()<<'\n';
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[89d9fb3a0aa3436d85b758035ffeadea.png]: https://img-blog.csdnimg.cn/89d9fb3a0aa3436d85b758035ffeadea.png
[8abf5d61438e40d099675d486197b608.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3bb219ae07314012ae0d776b0936431c.png