E - Souvenir
https://atcoder.jp/contests/abc286/tasks/abc286_e
思想
图计算Floyd算法,求任意两点之间的最短距离
最短距离对应路径上value总和。
Floyd算法理解
https://www.cnblogs.com/lightsong/p/16974935.html
Floyd算法为甚k在最外层:
https://www.zhihu.com/question/30955032
Code
https://atcoder.jp/contests/abc286/submissions/38269764
#include <bits/stdc++.h> using namespace std; map<int, vector<int>>mp; /* dp[i][j][k] i = 0 --> n-1 start city j = 0 --> n-1 end city k = 0 --> 1 dp[i][j][0] -- the number of segments of shortest road from city i to city j dp[i][j][1] -- the accumulated value one the shortest road by souvenir */ long long dp[304][304][2]; int main(){ int n; cin>>n; vector<long long> v(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j][0]=n; } } for(int i=0;i<n;i++){ cin>>v[i]; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ char c; cin>>c; if(c=='Y'){ mp[i].push_back(j); } } } for(int i=0; i<n; i++){ for(int j=0;j<mp[i].size();j++){ dp[i][mp[i][j]][0]=1; dp[i][mp[i][j]][1]=v[i]+v[mp[i][j]]; } dp[i][i][0]=0; dp[i][i][1]=v[i]; } for(int k=0; k<n; k++){ for(int i=0;i<n;i++){ if (k==i){ continue; } for(int j=0;j<n;j++){ if (k==i){ continue; } if(i==j){ continue; } if(dp[i][j][0]>dp[i][k][0]+dp[k][j][0]){ dp[i][j][0]=dp[i][k][0]+dp[k][j][0]; dp[i][j][1]=dp[i][k][1]+dp[k][j][1]-v[k]; } else if(dp[i][k][0]+dp[k][j][0]==dp[i][j][0]){ dp[i][j][1]=max(dp[i][j][1],dp[i][k][1]+dp[k][j][1]-v[k]); } } } } int q; cin>>q; while(q--){ int a,b; cin>>a>>b; a--;b--; if(dp[a][b][0]==n){ cout<<"Impossible"<<endl; }else{ cout<<dp[a][b][0]<<" "<<dp[a][b][1]<<endl; } } }
原文链接: https://www.cnblogs.com/lightsong/p/17064826.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/313572
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!