HDU 1690 Bus System：Floyd-Warshall 多源最短路

問題描述

n ≤ 100 個車站，位置坐標 place[i]。票價分段：距離 d 落在 (L_{k-1}, L_k] 區間收費 C_k（k=1..4），超出 L_4 不可達。站點間若可達則邊權為票價。m 條查詢，求最小花費。

建圖與 Floyd

• 任意兩站 i, j 距離 |place[i]-place[j]|，查表得票價 cost(i,j)
• 若超出 L_4 則 INF
• Floyd-Warshall 計算全對最短路：dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
• 查詢直接輸出 dis[s][t]

參考代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
typedef long long LL;
const LL INF = 1e15;

LL dis[N][N], place[N];
LL L1, L2, L3, L4, C1, C2, C3, C4;
int n, m;

LL cost(LL d) {
    if (d < 0) d = -d;
    if (d > 0 && d <= L1) return C1;
    else if (d <= L2) return C2;
    else if (d <= L3) return C3;
    else if (d <= L4) return C4;
    return INF;
}

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][k] != INF && dis[k][j] != INF)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%lld%lld%lld%lld%lld%lld%lld%lld", &L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%lld", &place[i]);
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++)
                dis[i][j] = dis[j][i] = cost(place[i] - place[j]);
        for (int i = 1; i <= n; i++) dis[i][i] = 0;
        floyd();
        printf("Case %d:\n", cas);
        for (int i = 0; i < m; i++) {
            int s, t; scanf("%d%d", &s, &t);
            if (dis[s][t] != INF)
                printf("The minimum cost between station %d and station %d is %lld.\n", s, t, dis[s][t]);
            else
                printf("Station %d and station %d are not attainable.\n", s, t);
        }
    }
    return 0;
}

複雜度

• 建圖：O(n²)
• Floyd：O(n³)，n=100 → 1e6 操作，極快
• 查詢：O(1)

關鍵點

1. 完整圖（任意兩站直達），邊權由距離分段函數決定
2. Floyd 適用於小規模稠密圖全對最短路
3. 用 long long 防止距離累加溢出