AT_abc286e 题解

首先观察到 \(n \leq 300\) 加上全源“最短路”便可以自然而然的想到 floyd。

注意到 floyd 算法的可行性只依赖统计的东西具有优先级。

这里我们定义优先级为最短路最短且价值和最高。也就是在最短路相同的情况下比较价值和。

然后跑一遍 floyd 板子即可，复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
const int maxn =301;
pair<int,int> dp[maxn][maxn];
int a[maxn];
int n;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        char c;
        cin>>c;
        dp[i][j]=make_pair(c=='Y'?1:inf,c=='Y'?a[i]+a[j]:0);
        if(i==j) dp[i][j]=make_pair(0,a[i]);
    }
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&i!=k&&j!=k)
            {
                pair<int,int> New=make_pair(dp[i][k].first+dp[k][j].first,dp[i][k].second+dp[k][j].second-a[k]);
                if(New.first<dp[i][j].first||(New.first==dp[i][j].first&&New.second>dp[i][j].second))
                    dp[i][j]=New;
            }

int t;
cin>>t;
while(t--)
{
    int u,v;
    cin>>u>>v;
    if(dp[u][v].first!=inf) cout<<dp[u][v].first<<' '<<dp[u][v].second<<'\n';
    else cout<<"Impossible\n";
}
}