题目描述

难度分:$1128$

输入$n(2 \leq n \leq 300)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，表示一个$n$个点的图，每个点的点权为$a[i]$。

然后输入一个$n \times n$的YN矩阵$g$，其中$g[i][j]=$Y表示有一条从$i$到$j$的有向边，边权为$1$；$g[i][j]=$N表示没有$i$到$j$的有向边。保证$g[i][i]=$N。

然后输入$q(1 \leq q \leq n \times (n-1))$和$q$个询问，每个询问输入两个数$x$和$y$，保证$x \neq y$，范围在$[1,n]$。

对于每个询问，输出两个数：

1. 从$x$到$y$的最短路长度$d$。
2. 在所有从$x$到$y$的长为$d$的路径中，路径点权之和的最大值。

如果无法从$x$到$y$，输出Impossible。

输入样例$1$

5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5

输出样例$1$

1 100
2 160
3 180

输入样例$2$

2
100 100
NN
NN
1
1 2

输出样例$2$

Impossible

算法

$Floyd$算法

比较容易想到用$Floyd$算法来求多源汇最短路，因为它的本质是动态规划，扩展性还是蛮强的。假设$dist[x][y]$是$x$到$y$的最短路，$w[x][y]$是$x$到$y$在保持最短路的情况下的最大点权和。

1. 如果$dist[i][j] \gt dist[i][k]+dist[k][j]$，那么进行状态转移$dist[i][j]=dist[i][k]+dist[k][j]$，$w[i][j]=w[i][k]+w[k][j]-a[k]$。减去$a[k]$是因为这个状态转移下，中间点$k$的权值被加了两次，需要减去一次。
2. 如果$dist[i][j]=dist[i][k]+dist[k][j]$，那么进行状态转移$w[i][j]=max(w[i][j],w[i][k]+w[k][j]-a[k])$。

之后$q$个查询，每个$O(1)$就可以从$w$矩阵中查到答案。

复杂度分析

时间复杂度

$Floyd$算法的时间复杂度为$O(n^3)$。每条询问的处理是$O(1)$的，处理所有询问的时间复杂度为$O(q)$。因此，整个算法的时间复杂度为$O(n^3+q)$。

空间复杂度

除了输入的点权数组$a$和图的邻接矩阵$g$，空间消耗的瓶颈在于$w$和$dist$两个矩阵，额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 310, INF = 0x3f3f3f3f;
char s[N][N];
int n, a[N], dist[N][N];
LL w[N][N];

int main() {
    scanf("%d", &n);
    memset(w, 0, sizeof w);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= n; j++) {
            if(s[i][j] == 'Y') {
                dist[i][j] = 1;
                w[i][j] = max(w[i][j], 1LL * a[i] + a[j]);
            }else {
                dist[i][j] = INF;
            }
        }
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    w[i][j] = w[i][k] + w[k][j] - a[k];
                }else if(dist[i][k] + dist[k][j] == dist[i][j]) {
                    w[i][j] = max(w[i][j], w[i][k] + w[k][j] - a[k]);
                }
            }
        }
    }
    int q;
    scanf("%d", &q);
    while(q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if(dist[x][y] < INF) {
            printf("%d %lld\n", dist[x][y], w[x][y]);
        }else {
            puts("Impossible");
        }
    }
    return 0;
}