ABC286E弗洛伊德边数最少点权最大

#include <bits/stdc++.h>
using namespace std;
const long long N=305, M=5e12; 
int n, m, i, j, k, x, y, a[N];
long long f[N][N], p, q;
char s[N];
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(f, -2, sizeof(f));//求最大值，默认无穷小
    for(i=1; i<=n; i++){
        scanf("%s", s+1);
        for(j=1; j<=n; j++){
            if(s[j] == 'Y'){
                f[i][j] = -M + a[i] + a[j];
            }//有边，边权为点权和
        }//因为尽量少边，每条边扣除M费用
    }
    for(k=1; k<=n; k++){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                f[i][j] = max(f[i][j], f[i][k]+f[k][j]-a[k]);
            }
        }
    }//弗洛伊德求最长路，点权和不超过M，保证边最少 
    scanf("%d", &m);
    while(m--){
        scanf("%d%d", &x, &y);
        if(f[x][y] == f[0][0]) printf("Impossible\n");
        else{
            q = f[x][y] % M + M;//负数转正 
            p = (f[x][y]-q) / M;//向上取整 
            printf("%lld %lld\n", -p, q);
        }//分解出边数和点权和 
    }
    return 0;
}