T1. 道路

題目鏈接：SOJ D1216

$N$ 個以 $1～N$ 標號的城市通過單向的道路相連，每條道路包含兩個參數：道路的長度和需要為該路付的通行費（以金幣的數目來表示）。

Bob 和 Alice 過去住在城市 $1$，在注意到 Alice 在他們過去喜歡玩的紙牌游戲中作弊后，Bob 和她分手了，并且決定搬到城市 $N$。他希望能夠盡可能快的到那，但是他囊中羞澀。我們希望能夠幫助 Bob 找到從 $1$ 到 $N$ 最短的路徑，前提是他能夠付的起通行費。

時間限制：1 s
內存限制：64 MB

• 輸入
  第一行包含一個整數 $K$，$0\le K\le 10000$，代表 Bob 能夠在他路上花費的最大的金幣數。
  第二行包含整數 $N$，$2\le N\le 100$，指城市的數目。
  第三行包含整數 $R$，$1\le R\le 10000$，指路的數目。
  接下來的 $R$ 行，每行具體指定幾個整數 $S,D,L$ 和 $T$ 來說明關于道路的一些情況，這些整數之間通過空格間隔：$S$ 是道路起始城市，$1\le S\le N$，$D$ 是道路終點城市，$1\le D\le N$，$L$ 是道路長度，$1\le L\le 100$，$T$ 是通行費（以金幣數量形式度量），$0\le T\le 100$。注意不同的道路可能有相同的起點和終點。
• 輸出
  輸入結果應該只包括一行，即從城市 $1$ 到城市 $N$ 所需要的最小的路徑長度（花費不能超過 $K$ 個金幣）。如果這樣的路徑不存在，結果應該輸出 $?1$。
• 樣例輸入

  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
  

思路分析

此題考查圖論最短路徑問題，是一道較好的基礎應用題。

在數據量較小的情況下（大約 $N\le 1000$），最短路徑問題可以用 $\mathtt{BFS}$ 進行求解，更快速的方式是使用堆優化的 $\mathtt{Dijkstra}$ 算法。示例代碼采用鏈式前向星存圖，用堆（優先隊列替代）優化的 $\mathtt{Dijkstra}$ 算法求解最短路，通過運算符重載來規定優先隊列中成員的優先級。

此題涉及到代價和距離兩個屬性，應以距離為第一優先級參數，距離相同時，考慮代價為第二優先級參數。需要注意的是，優先隊列默認為大根堆，可以通過重載小于號 < 實現小根堆，其中距離較長的元素的優先級高于距離較短者，代價較高的元素的優先級高于代價較低者（也可以通過給參與優先級比較的成員添加負號 - 來實現小根堆，免去運算符重載的麻煩）。

常規 $\mathtt{Dijkstra}$ 算法通過定義 $dist$ 數組存儲從起點到每個點的最短路徑長度，來限制只有更新了最短路徑長度的頂點入隊。此題應該限制代價不超過 $k$ 的元素入隊，與最短路徑更新與否無關，因為距離最短的路徑的總代價并不一定支付得起。也正因如此，每個頂點可能被其它代價更小的路徑再次訪問，不能添加標記數組對頂點進行分類。

/** Name: T1.cpp* Problem: 道路* Author: Teacher Gao.* Date&Time: 2025/05/14 22:48*/#include <bits/stdc++.h>using namespace std;// 鏈式前向星的數據結構
int to[10005], wl[10005], wt[10005], nxt[10005];
int head[105], tot;void add_edge(int x, int y, int w1, int w2) {++tot;to[tot] = y, wl[tot] = w1, wt[tot] = w2;	// 存儲邊信息nxt[tot] = head[x], head[x] = tot;			// 頭插法
}int k, n, m;// 用于優先隊列的數據結構
struct node {int dis, cost, id;bool operator < (const node &a) const {		// 重載小于號if (dis != a.dis) return dis > a.dis;	// 第一優先級return cost > a.cost;					// 第二優先級}
};int dijkstra(int s) {priority_queue<node> Q;Q.push({0, 0, 1});while (Q.size()) {node x = Q.top(); Q.pop();if (x.id == n) {return x.dis;}for (int i = head[x.id]; i; i = nxt[i]) {if (x.cost + wt[i] <= k) {Q.push({x.dis + wl[i], x.cost + wt[i], to[i]});}}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(