題干：

給你n個(gè)點(diǎn)，m條無(wú)向邊，每條邊都有長(zhǎng)度d和花費(fèi)p，給你起點(diǎn)s終點(diǎn)t，要求輸出起點(diǎn)到終點(diǎn)的最短距離及其花費(fèi)，如果最短距離有多條路線，則輸出花費(fèi)最少的。

Input

輸入n,m，點(diǎn)的編號(hào)是1~n,然后是m行，每行4個(gè)數(shù) a,b,d,p，表示a和b之間有一條邊，且其長(zhǎng)度為d，花費(fèi)為p。最后一行是兩個(gè)數(shù) s,t;起點(diǎn)s，終點(diǎn)。n和m為0時(shí)輸入結(jié)束。?
(1<n<=1000, 0<m<100000, s != t)

Output

輸出 一行有兩個(gè)數(shù)， 最短距離及其花費(fèi)。

Sample Input

3 2 1 2 5 6 2 3 4 5 1 3 0 0

Sample Output

9 11

解題報(bào)告：

? ? ? 最短路的雙權(quán)值問(wèn)題，優(yōu)先級(jí)高的滿足小于關(guān)系的時(shí)候，對(duì)于優(yōu)先級(jí)低的需要無(wú)腦加，當(dāng)優(yōu)先級(jí)高的相等的時(shí)候優(yōu)先級(jí)較低的才可以取min ?。

AC代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 1000 + 5; const int INF = 0x3f3f3f3f; int cost[MAX],dis[MAX]; bool vis[MAX]; int head[MAX]; int n,m; int cnt; int st,ed; //w代表距離，c代表花費(fèi) struct Edge {int to,w,ne,c; } e[100000 + 5]; struct Point {int pos;int w,c;Point(){}Point(int pos,int w,int c):pos(pos),w(w),c(c){}bool operator<(const Point & b) const {return w>b.w;} } p; void Dijkstra(int u,int v) {dis[u] = 0;cost[u] = 0;int all = n,minw = INF,minv;priority_queue<Point> pq;pq.push(Point(u,0,0));while(!pq.empty()) { // printf("...\n");Point cur = pq.top();pq.pop(); // if(vis[cur.pos] == 1) continue;//加不加都可以 vis[cur.pos] = 1;if(cur.pos == v) break;int x = cur.pos;for(int i = head[x]; i!=-1; i=e[i].ne) { // if(vis[e[i].to] == 1) continue; 這句千萬(wàn)不能加。。。 if(dis[e[i].to] > dis[x] + e[i].w ) {dis[e[i].to] = dis[x] + e[i].w;cost[e[i].to] = cost[x] + e[i].c;pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}else if(dis[e[i].to] == dis[x] + e[i].w) {cost[e[i].to] = min(cost[e[i].to] , cost[x] + e[i].c);pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));} // if(vis[e[i].to ] == 0) // pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to])); }}printf("%d %d\n",dis[v],cost[v]); } void add(int a,int b,int w,int c) {e[cnt].to = b;e[cnt].w = w;e[cnt].c = c; e[cnt].ne = head[a];head[a] = cnt++; } void init() {cnt = 0;memset(head,-1,sizeof(head));memset(dis,INF,sizeof(dis));memset(cost,INF,sizeof(cost));memset(vis,0,sizeof(vis)); } int main() {int a,b,d,p;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();while(m--) {scanf("%d%d%d%d",&a,&b,&d,&p);add(a,b,d,p);add(b,a,d,p);}scanf("%d%d",&st,&ed);Dijkstra(st,ed); }return 0 ; }

MLE代碼：（就是push的位置不同，，就會(huì)MLE）

?

//改一下push的位置 能過(guò)嗎？ #include<bits/stdc++.h>using namespace std; const int MAX = 1000 + 5; const int INF = 0x3f3f3f3f; int cost[MAX],dis[MAX]; bool vis[MAX]; int head[MAX]; int n,m; int cnt; int st,ed; //w代表距離，c代表花費(fèi) struct Edge {int to,w,ne,c; } e[100000 + 5]; struct Point {int pos;int w,c;Point(){}Point(int pos,int w,int c):pos(pos),w(w),c(c){}bool operator<(const Point & b) const {return w>b.w;} } p; void Dijkstra(int u,int v) {dis[u] = 0;cost[u] = 0;int all = n,minw = INF,minv;priority_queue<Point> pq;pq.push(Point(u,0,0));while(!pq.empty()) { // printf("...\n");Point cur = pq.top();pq.pop(); // if(vis[cur.pos] == 1) continue;//加不加都可以 vis[cur.pos] = 1;if(cur.pos == v) break;int x = cur.pos;for(int i = head[x]; i!=-1; i=e[i].ne) { // if(vis[e[i].to] == 1) continue; 這句千萬(wàn)不能加。。。 if(dis[e[i].to] > dis[x] + e[i].w ) {dis[e[i].to] = dis[x] + e[i].w;cost[e[i].to] = cost[x] + e[i].c; // pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}else if(dis[e[i].to] == dis[x] + e[i].w) {cost[e[i].to] = min(cost[e[i].to] , cost[x] + e[i].c); // pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}if(vis[e[i].to ] == 0) pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to])); }}printf("%d %d\n",dis[v],cost[v]); } void add(int a,int b,int w,int c) {e[cnt].to = b;e[cnt].w = w;e[cnt].c = c; e[cnt].ne = head[a];head[a] = cnt++; } void init() {cnt = 0;memset(head,-1,sizeof(head));memset(dis,INF,sizeof(dis));memset(cost,INF,sizeof(cost));memset(vis,0,sizeof(vis)); } int main() {int a,b,d,p;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();while(m--) {scanf("%d%d%d%d",&a,&b,&d,&p);add(a,b,d,p);add(b,a,d,p);}scanf("%d%d",&st,&ed);Dijkstra(st,ed); }return 0 ; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【HDU - 3790】最短路径问题（DIjkstra算法 双权值）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。