---
title: "AtCoder Beginner Contest 286 E(最短路)"
tags: 題解, 演算法, 圖論
---

https://atcoder.jp/contests/abc286/tasks/abc286_e

#### 題意

給一個 $n$ x $n$ 的矩陣代表兩個節點是否相連，再給一個 $A[i]$ 代表第 $i$ 個節點上的分數。接下來有 $Q$ 筆詢問，每筆詢問為 $u$、$v$ 兩節點之間「最短節點數的路徑之節點數」以及「所有長度為此節點數的路徑中，最大分數的路徑之分數」。

#### 思路

一般來說，使用 Floyd-Warshall 求全源最短路時，求的都是距離最短的路徑；這題特別的地方在於：除了最小化節點數以外，也要同時最大化路徑上的分數。

一個常見的做法是把每條邊的權重從 $w$ 轉化成 $C-w$，$C$ 是一個很大的數字。由於權重主要被 $C$ 主宰，找出的最短路必定會是節點數最少的；以同樣節點數的路徑而言，路徑上權重和 $\sum{w}$ 較大，則整條路徑的 $\sum{(C-w)}$會是最小，使得它會被選為最短路。如此，藉由增加一個大數字主宰邊的權重，即可同時最小化節點數以及最大化路徑分數和。

計算路徑的節點數時，假設節點數為 $n$，路徑分數和就會是 $nC - \sum{w}$，將其除以 $C$ 並取 ceil 即可得到 $n$。路徑真實的分數和則為 $nC - (nC - \sum{w})$。

#### Code

def floyd(n, G):
    dist = [[INF for _ in range(n)] for _ in range(n)]
    prev = [[-1 for _ in range(n)] for _ in range(n)]
    for (u, v, w) in G:
        dist[u][v] = w
        prev[u][v] = u
    for v in range(n):
        dist[v][v] = 0
        prev[v][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF and \
                        dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    prev[i][j] = prev[k][j]
    return dist, prev

def solve(_tc):
    n = int(input())
    A = list(map(int, input().split()))

    offset = 10 ** 13

    graph = []
    for i in range(n):
        s = input()
        for (j, can) in enumerate(s):
            if can == "Y":
                graph.append((i, j, offset - A[j]))

    D, _ = floyd(n, graph)

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        ans = D[u][v]
        if ans == INF:
            print("Impossible")
        else:
            num = ans // offset + int(ans % offset != 0)
            value = offset * num - ans + A[u]
            print(num, value)