博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU3790:最短路径问题(最短路+双权值)
阅读量:7314 次
发布时间:2019-06-30

本文共 2640 字,大约阅读时间需要 8 分钟。

最短路径问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24687    Accepted Submission(s): 7360


Problem Description
给你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
 

Source
 

Recommend
notonlysuccess
这里采用dijkstra算法。
# include 
# include
# include
# define INF 0x3f3f3f3fusing namespace std;int dis[1001][1001], cost[1001][1001], vis[1001], lowcost[1001], lowvalue[1001];int ans1, ans2;void dijkstra(int n, int s, int t){ memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; ++i) { lowcost[i] = dis[s][i]; lowvalue[i] = cost[s][i]; } vis[s] = 1; for(int i=2; i<=n; ++i) { int minid, imin = INF, imin2 = INF; for(int j=1; j<=n; ++j) { if(!vis[j]) { if(lowcost[j] < imin) { imin = lowcost[j]; imin2 = lowvalue[j]; minid = j; } else if(lowcost[j] == imin) imin2 = min(imin2, lowvalue[j]); } } if(imin == INF) break; vis[minid] = 1; for(int j=1; j<=n; ++j) { if(!vis[j]) { if(dis[j][minid]+lowcost[minid] < lowcost[j]) { lowcost[j] = dis[j][minid] + lowcost[minid]; lowvalue[j] = cost[j][minid] + lowvalue[minid]; } else if(dis[j][minid]+lowcost[minid] == lowcost[j]) lowvalue[j] = min(lowvalue[j], cost[j][minid] + lowvalue[minid]); } } } ans1 = lowcost[t]; ans2 = lowvalue[t];}int main(){ int n, m, a, b, d, p, s, t; while(~scanf("%d%d",&n,&m),n+m) { for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) dis[i][j] = dis[j][i] = cost[i][j] = cost[j][i] = INF; while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(dis[a][b] > d) { dis[a][b] = dis[b][a] = d; cost[a][b] = cost[b][a] = p; } else if(dis[a][b] == d) if(cost[a][b] > p) cost[a][b] = cost[b][a] = p; } scanf("%d%d",&s,&t); dijkstra(n, s, t); printf("%d %d\n",ans1, ans2); }}

转载于:https://www.cnblogs.com/junior19/p/6730000.html

你可能感兴趣的文章
指数预测模型
查看>>
我的友情链接
查看>>
利用Diskpart分区
查看>>
Lync Server 2013企业版部署测试一:资源、DNS、环境准备
查看>>
linux高可用集群(HA)原理详解
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
RHEL7->第二章 LVM创建
查看>>
诺基亚日本损落,下一步何去何从
查看>>
edx 课程页面 (包括讨论) 相关代码
查看>>
linux免密码SSH和SCP
查看>>
你必须非常努力,才能看起来毫不费力
查看>>
编码原理详解(四)---之字形扫描
查看>>
mysql之主从、主主同步
查看>>
Leetcode PHP题解--D21 344. Reverse String
查看>>
遮罩层
查看>>
AxureRP7.0基础教程系列 部件详解 文本框 Text field
查看>>
使用lxc提供轻量级虚拟化
查看>>
shell 脚本之转置文件
查看>>
软路由实践
查看>>