POJ 1062 昂貴的聘禮：等級限制下的最短路變體

問題背景

探險家要用最少金幣娶到酋長女兒。物品編號 1..N（1 號為酋長承諾），每個物品有原價 P、主人等級 L、若干替代品 (T, V) 表示用物品 T 可按價 V 購買。交易規則：任意兩人等級差 > M 不得直接/間接交易；探險家初始無等級限制，但一旦與某等級交易，超出 M 範圍的等級將拒絕後續交易。求得到物品 1 的最小花費。

建模：虛擬源點 + 等級窗口枚舉 + Dijkstra

• 建立有向圖：邊 T → i 權重 V 表示用 T 換 i；虛擬源點 0 向每個物品 i 連邊權 P_i 表示直接買。
• 等級限制意味著：所有參與交易的物品等級必須落在某個長度為 M 的區間 [L_min, L_min+M] 內。
• 枚舉區間下界 L_min 為每個物品的等級，構建子圖只保留等級在 [L_min, L_min+M] 的點，跑 Dijkstra 求 0→1 最短路，取全局最小值。

算法細節

// 圖用鄰接矩陣 tu[u][v] 存儲最小權重
// price[i] 為從源點 0 到 i 的當前最短距離
// visit[i] 標記節點是否在當前等級窗口內且未最終確定
// 簡化版 Dijkstra（N≤100，O(N^2) 足夠）:
for i=1..N: price[i]=tu[0][i];
repeat N times:
    找未確定的 visit[j]=true 且 price[j] 最小的 u
    visit[u]=false;
    對所有 visit[v]=true: price[v]=min(price[v], price[u]+tu[u][v]);
答案為 price[1]

複雜度

• 枚舉 N 個等級窗口
• 每窗口 Dijkstra O(N^2)
• 總計 O(N^3) = 10^6 量級，極快。

完整參考代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int tu[105][105], price[105], level[105];
bool visit[105];
int n, m;
int dijkstra() {
    for(int i=1;i<=n;i++) price[i]=tu[0][i];
    memset(visit, true, sizeof(visit));
    visit[0]=false;
    for(int iter=1; iter<=n; iter++){
        int u=0, mn=1e9;
        for(int j=1;j<=n;j++) if(visit[j] && price[j]>m>>n){
        memset(tu,0,sizeof(tu));
        for(int i=1;i<=n;i++){
            int k; cin>>price[i]>>level[i]>>k;
            tu[0][i]=price[i];
            for(int j=0;j>v>>p;
                tu[v][i]=p; // v -> i
            }
        }
        int ans=1e9;
        for(int i=1;i<=n;i++){
            int L=level[i];
            for(int j=1;j<=n;j++)
                visit[j] = (level[j]>=L && level[j]<=L+m);
            ans=min(ans, dijkstra());
        }
        cout<