Submission #38203516

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
int arr[301];
char mp[301][301];
pll dist[301][301];
const ll INF = 1LL<<60;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N; cin>>N;
    for(int i=0;i<N;i++){
        cin>>arr[i];
    }
    for(int i=0;i<N;i++) cin>>mp[i];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(mp[i][j] == 'N') dist[i][j] = {INF, 0};
            else dist[i][j] = {1, arr[i] + arr[j]};
        } 
        dist[i][i] = {0, arr[i]};
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                pll np = {dist[j][i].first + dist[i][k].first, dist[j][i].second + dist[i][k].second - arr[i]};
                if(np.first < dist[j][k].first){
                    dist[j][k] = np;
                }
                else if(np.first == dist[j][k].first) dist[j][k].second = max(np.second, dist[j][k].second);
            }
        }
    }
    int Q;
    cin>>Q;
    while(Q--){
        int s, t;
        cin>>s>>t;
        s--;
        t--;
        auto [a, b] = dist[s][t];
        if(a == INF) cout<<"Impossible\n";
        else cout<<a<<' '<<b<<'\n';
    }
}

Submission Info

Judge Result