思路：对于有很多询问的题，一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。文章来源：https://www.toymoban.com/news/detail-822401.html
代码：文章来源地址https://www.toymoban.com/news/detail-822401.html
#include <bits/stdc++.h>
#define pb push_back
#define a first
#define b second
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef unsigned long long ull;
char str[1005];
int main(){
int n;
scanf("%d",&n);
vector <ll> A(n);
for(int i=0;i<n;i++) scanf("%lld",&A[i]);
vector < vector<int> > mp(n);
for(int i=0;i<n;i++){
scanf("%s",&str);
mp[i].resize(n);
for(int j=0;j<n;j++){
mp[i][j]=str[j]=='Y';
}
mp[i][i]=1;
}
ll inf=1000000000000000;
vector < vector<ll> > ans(n);
vector < vector<int> > vd(n);
for(int i=0;i<n;i++){
ans[i].resize(n);
for(int j=0;j<n;j++) ans[i][j]=-inf;
vector <int> dist(n,n+1);
queue <int> que;
dist[i]=0;
ans[i][i]=A[i];
que.push(i);
while(!que.empty()){
int v=que.front();que.pop();
for(int j=0;j<n;j++){
if(mp[v][j]){
if(dist[j]==n+1){
dist[j]=dist[v]+1;
que.push(j);
}
if(dist[j]==dist[v]+1){
ans[i][j]=max(ans[i][j],ans[i][v]+A[j]);
}
}
}
}
vd[i]=dist;
}
int Q;
scanf("%d",&Q);
for(int i=0;i<Q;i++){
int u,v;
scanf("%d%d",&u,&v);u--,v--;
if(ans[u][v]==-inf) puts("Impossible");
else printf("%d %lld\n",vd[u][v],ans[u][v]);
}
}到了这里，关于E - Souvenir(图论典型例题)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[算法]动态规划以及常见例题](https://imgs.yssmx.com/Uploads/2024/02/758610-1.png)
