分道揚鑣：費用受限最短路徑問題（DFS 強剪枝 C 實作）

分道揚鑣：費用受限最短路徑問題（DFS 強剪枝 C 實作）

問題描述：N 個城市（1..N），R 條有向道路，每條道路有長度 L 和費用 T。從城市 1 出發到城市 N，總費用 ≤ K，求最短路徑長度；不存在輸出 -1。

• K ≤ 10,000（最大費用）
• N ≤ 100（城市數）
• R ≤ 10,000（道路數）
• L ≤ 100，T ≤ 100
• 可能有重邊、自環

演算法選擇：DFS + 三重剪枝

雖然 Dijkstra 可解單一約束最短路，但「費用上限 + 長度最小」的雙目標約束使其難以直接適用。DFS 搜索所有可行路徑，配合強剪枝，在 N≤100、稀疏圖下極具競爭力。

三重剪枝策略

1. 費用剪枝：當前累積費用 ck + edge.cost > K → 直接放棄
2. 距離剪枝：當前累積距離 currDist + edge.dist ≥ bestDist → 無法優化最優解，放棄
3. 訪問標記：visited[v] 防止環路，單條路徑不重複訪問節點

資料結構：鄰接表

typedef struct {
    int dist, cost;
} WeightType;

typedef struct AdjVNode {
    int adjV;           // 鄰接點
    WeightType weight;  // 距離、費用
    struct AdjVNode *next;
} AdjVNode;

typedef struct {
    AdjVNode *firstEdge;
} VNode;

typedef struct {
    int Nv, Ne;
    VNode G[101];  // 1-based 索引
} LGraph;

核心 DFS 實作

int K;           // 最大費用
int ck = 0;      // 當前費用
int currDist = 0; // 當前距離
int bestDist = INT_MAX;
bool visited[101];

int DFS(LGraph *G, int u) {
    if (u == G->Nv) {           // 到達目標城市 N
        if (currDist < bestDist) bestDist = currDist;
        return bestDist;
    }

    for (AdjVNode *e = G->G[u].firstEdge; e; e = e->next) {
        int v = e->adjV;
        if (!visited[v] && ck + e->weight.cost <= K && currDist + e->weight.dist < bestDist) {
            visited[v] = true;
            ck += e->weight.cost;
            currDist += e->weight.dist;

            DFS(G, v);

            ck -= e->weight.cost;
            currDist -= e->weight.dist;
            visited[v] = false;
        }
    }
    return bestDist;
}

完整主程式

#include 
#include 
#include 
#include 
#include 

#define MAXV 101

// ... 結構體定義同上 ...

LGraph* BuildGraph() {
    LGraph *G = calloc(1, sizeof(LGraph));
    int Nv, Ne;
    scanf("%d %d", &Nv, &Ne);
    G->Nv = Nv; G->Ne = Ne;

    for (int i = 1; i <= Nv; ++i) G->G[i].firstEdge = NULL;

    for (int i = 0; i < Ne; ++i) {
        int s, d, l, t;
        scanf("%d %d %d %d", &s, &d, &l, &t);
        AdjVNode *node = malloc(sizeof(AdjVNode));
        node->adjV = d;
        node->weight.dist = l;
        node->weight.cost = t;
        node->next = G->G[s].firstEdge;
        G->G[s].firstEdge = node;
    }
    return G;
}

int main() {
    scanf("%d", &K);
    LGraph *G = BuildGraph();

    memset(visited, 0, sizeof(visited));
    visited[1] = true;
    ck = currDist = 0;
    bestDist = INT_MAX;

    DFS(G, 1);

    if (bestDist == INT_MAX) printf("-1\n");
    else printf("%d\n", bestDist);

    // 釋放圖記憶體（略）
    return 0;
}

樣例測試

輸入：
5 6 7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

輸出：
11

路徑：1 → 3 (費用1,長度4) → 5 (費用0,長度2) → 4 (費用2,長度3) → 6 (費用1,長度2)
總費用 = 1+0+2+1 = 4 ≤ 5，總長度 = 4+2+3+2 = 11

複雜度分析與優化方向

進階優化

1. 啟發式排序：鄰接表按 dist/cost 比值升序，優先探索「性價比高」路徑，更快找到優質解收緊 bestDist
2. 備忘錄/動態規劃：狀態 dp[u][cost] = 從 u 到 N 費用≤cost 的最短距離，轉移 dp[u][c] = min(dist(u,v) + dp[v][c-cost(u,v)])，複雜度 O(N·K + E·K)
3. A* 搜索：引入啟發函數 h(u) = u 到 N 的無約束最短距離（預先跑一次反向 Dijkstra）

本題展示了在雙約束最短路問題中，DFS+剪枝作為基線解法的工程價值，同時指明了向 DP/A* 演進的優化路徑。