学向勤中得,萤窗万卷书。这篇文章主要讲述HDU - 3790最短路径问题(DIjkstra算法双权值)相关的知识,希望能为你提供帮助。
题干:
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;
起点s,终点。n和m为0时输入结束。
(1<
n<
=1000, 0<
m<
100000, s != t)
Output
输出 一行有两个数, 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
【HDU - 3790最短路径问题(DIjkstra算法双权值)】解题报告:
最短路的双权值问题,优先级高的满足小于关系的时候,对于优先级低的需要无脑加,当优先级高的相等的时候优先级较低的才可以取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代表花费
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; 这句千万不能加。。。
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",推荐阅读
- HDU - 5605 geometry(水,数学题,推公式)
- HDU - 3342Legal or Not(拓扑排序)
- HDU - 3499 Flight (单源最短路+优惠问题)
- POJ-3259 Wormholes(判负环,spfa算法)
- 树莓派开发笔记(十七)(树莓派4B+上Qt多用户连接操作Mysql数据库同步(单条数据悲观锁))
- 最全Redis数据类型使用场景总结
- POJ - 1502MPI Maelstrom(Dijkstra单源最短路--求一点到其余个点的最小值的最大值)
- *51nod - 1459迷宫游戏(记录双向权值的Dijkstra单源最短路)
- HDU - 2112 HDU Today(dijkstra单源最短路 + map转换)