ZeroJudge 解題筆記：k519. P7.機票 (Ticket)

作者：王一哲
日期：2025年5月4日



ZeroJudge 題目連結：k519. P7.機票 (Ticket)

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 個城市
    graph = [list(map(int, input().split())) for _ in range(n)]  # 讀取城市之前移動費用
    start, end = map(int, input().split())  # 起點、終點
    start -=1; end -= 1  # 配合索引值減 1
    for k in range(n):  # 以 k 為轉機地點
        for i in range(n):  # 以 i 為起點
            for j in range(n):  # 以 j 為終點
                if graph[i][k] == -1 or graph[k][j] == -1: continue  # k 等於 i 或 j，找下一組
                if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j] - 50:  # 如果 i 等於 j 或 i->j 成本大於 i->k->j -50
                    graph[i][j] = graph[i][k] + graph[k][j] - 50
    print(graph[start][end])  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;  // n 個城市
    while(scanf("%d", &n) != EOF) {
        int graph[n][n];  // 讀取城市之前移動費用
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) scanf("%d", &graph[i][j]);
        }
        int start, end; scanf("%d %d", &start, &end);  // 起點、終點
        start--; end--;  // 配合索引值減 1
        for(int k=0; k<n; k++) {  // 以 k 為轉機地點
            for(int i=0; i<n; i++) {  // 以 i 為起點
                for(int j=0; j<n; j++) {  // 以 j 為終點
                    if (graph[i][k] == -1 || graph[k][j] == -1) continue;  // k 等於 i 或 j，找下一組
                    if (graph[i][j] == -1 || graph[i][j] > graph[i][k] + graph[k][j] - 50) {  // 如果 i 等於 j 或 i->j 成本大於 i->k->j -50
                        graph[i][j] = graph[i][k] + graph[k][j] - 50;
                    }
                }
            }
        }
        printf("%d\n", graph[start][end]);  // 印出答案
    }
    return 0;
}