【最短路】Atcoder Beginner Contest 286----E

题目：E - Souvenir (atcoder.jp)

题解：首先这道题可以很容易看出来是求最短路。最开始自己是用bfs写的，出现了WA,TLE,RE等错误。

因为对于每种情况会有Q次询问，如果每次询问都跑一遍最短路就会TLE，所以可以把这到题看成是多源最短路，只需在询问前跑一遍Floyd即可。

代码：

Floyd遍历时因为不是先遍历中转点k哇了好多次

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef unsigned long long ULL;
const ll mod = 998244353;
const int N = 2e5 + 5;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
int d[305][305];
ll value[305][305];
int n;
ll a[305];
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(d[i][k]+d[k][j]<d[i][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    value[i][j]=value[i][k]+value[k][j]-a[k];
                }
                else if(d[i][k]+d[k][j]==d[i][j])
                {
                    value[i][j]=max(value[i][j],value[i][k]+value[k][j]-a[k]);
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    memset(value,0,sizeof(value));
    memset(d,0x3f,sizeof(d));
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        s=' '+s;
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;
            if(s[j]=='Y') {
                d[i][j]=1;
                value[i][j]=a[i]+a[j];
            }
        }
    }
    floyd();
    int q;
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        if(d[u][v]>n) cout<<"Impossible"<<endl;
        else cout<<d[u][v]<<" "<<value[u][v]<<endl;
    }
    return 0;
}