//State: POJ1724 Accepted 1188K 32MS C++ 1968B /* *題目大意： * 給定總費用，還有n個城市，m條邊，構成的圖為單向圖，然后 * m條邊有費用，還有距離，求從1->n的最小距離，要求走邊時 * 費用要小于邊的費用。 *解題思路： * 用二維dij即可。 */ View Code #include <queue> #include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std;const int MAXN = 105; const int MAXE = 10005; const int MAX_COST = 10005; const int inf = 0x3f3f3f3f;typedef struct _node {int v, next;int l, c; }N; N edge[MAXE]; int cntEdge, head[MAXN];typedef struct _no {int v;int c, dis;_no(): dis(inf) {}_no(int a, int b, int c1): v(a), dis(b), c(c1) {} friend bool operator < (const struct _no &n1, const struct _no &n2){return n1.dis > n2.dis;} }priN;void init() {cntEdge = 0;for(int i = 0; i < MAXN; i++)head[i] = -1; }void addEdge(int u, int v, int l, int c) {edge[cntEdge].v = v;edge[cntEdge].l = l;edge[cntEdge].c = c;edge[cntEdge].next = head[u];head[u] = cntEdge++; }int dis[MAXN]; int dijkstra(int s, int n, int tol)//1是起點，n是終點 {int vst[MAXN] = {0};for(int i = 0; i <= n; i++)dis[i] = inf;priority_queue<priN> Q;Q.push(priN(s, 0, 0));//dis[s] = 0;while(!Q.empty()){priN pre = Q.top();Q.pop();if(pre.v == n)return pre.dis;for(int f = head[pre.v]; f != -1; f = edge[f].next){int son = edge[f].v;int l = edge[f].l;int c = edge[f].c;if(pre.c + c <= tol){//dis[son] = dis[pre.v] + l;Q.push(priN(son, pre.dis + l, pre.c + c));}}}return -1; }int main(void) { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, tol;while(scanf("%d", &tol) == 1){int m;scanf("%d %d", &n, &m);init();int u, v, l, c;for(int i = 0; i < m; i++){scanf("%d %d %d %d", &u, &v, &l, &c);addEdge(u, v, l, c);}int sol = dijkstra(1, n, tol);printf("%d\n", sol);}return 0; }

轉載于:https://www.cnblogs.com/cchun/archive/2012/09/02/2667588.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的POJ1724 ROADS 费用最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。