HDU 1690 完整解析：Floyd 全點對最短路

N 個站點，站點間距離決定票價：分段計價函數。多組查詢求任意兩站間最小花費。N ≤ 100，Floyd O(N³) 完全足夠。

票價函數

距離 d = |h[i] - h[j]|：

• d = 0：免費
• 0 < d ≤ L1：C1
• L1 < d ≤ L2：C2
• L2 < d ≤ L3：C3
• L3 < d ≤ L4：C4
• d > L4：不可達（INF）

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e12;
long long dist[1200][1200];
long long h[1200];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        long long L1, L2, L3, L4, C1, C2, C3, C4;
        cin >> L1 >> L2 >> L3 >> L4 >> C1 >> C2 >> C3 >> C4;
        int n, m; cin >> n >> m;
        
        for (int i = 1; i <= n; i++) cin >> h[i];
        
        // 初始化距離矩陣
        for (int i = 1; i <= n; i++) {
            dist[i][i] = 0;
            for (int j = 1; j < i; j++) {
                long long d = llabs(h[i] - h[j]);
                long long cost;
                if (d == 0) cost = 0;
                else if (d > L4) cost = INF;
                else if (d > L3) cost = C4;
                else if (d > L2) cost = C3;
                else if (d > L1) cost = C2;
                else cost = C1;
                dist[i][j] = dist[j][i] = cost;
            }
        }
        
        // Floyd
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        
        cout << "Case " << tc << ":\n";
        for (int i = 0; i < m; i++) {
            int a, b; cin >> a >> b;
            if (dist[a][b] >= INF/2)
                cout << "Station " << a << " and station " << b << " are not attainable.\n";
            else
                cout << "The minimum cost between station " << a << " and station " << b << " is " << dist[a][b] << ".\n";
        }
    }
    return 0;
}

關鍵點總結

• 分段計價：預計算所有點對直接花費
• Floyd 適用性：N=100，N³=1e6 極快，且需全點對查詢
• 長整型：花費累加可能超 int，用 long long
• 輸出格式：完全匹配題目要求的英文句子