博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 3790 (最短路径问题dijkstra)
阅读量:5828 次
发布时间:2019-06-18

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

主题链接:

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
代码例如以下:
#include 
#include
#include
#define MAXN 1017#define INF 0x3fffffffusing namespace std;int mat[MAXN][MAXN];int cost[MAXN][MAXN];int n,m;//n为结点数。m为道路数int MONEY[MAXN];int dijkstra (int s,int f){ //s为起点。 f:为终点 int dis[MAXN];//记录到随意点的最短距离 int mark[MAXN];//记录被选中的结点 int i, j, k; for(i = 1; i <= n; i++) { mark[i] = 0;//初始化全部结点。每一个结点都没有被选中 dis[i] = mat[s][i]; MONEY[i] = cost[s][i]; } mark[s] = 1;//start结点被选中 dis[s] = 0;//将start结点的的距离设置为0 int min;//设置最短的距离。 for(i = 1; i <= n; i++) { k = 1;//赋初值非常重要 min = INF; for(j = 1; j <= n;j++) { if(mark[j] == 0 && dis[j] < min)//未被选中的结点中,距离最短的被选中 { min = dis[j] ; k = j; } } mark[k] = 1;//标记为被选中 for(j = 1; j <= n; j++) { if(!mark[j] && dis[j]>dis[k]+mat[k][j])//改动剩余结点的最短距离 { dis[j] = dis[k] + mat[k][j]; MONEY[j]=MONEY[k]+cost[k][j]; } else if(!mark[j] && dis[j]==dis[k]+mat[k][j]) { if(MONEY[j] > MONEY[k]+cost[k][j]) MONEY[j] = MONEY[k]+cost[k][j]; } } } return dis[f]; } void init(){ for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cost[i][j] = INF; if(i == j) mat[i][j] = 0; else mat[i][j] = INF; } }}int main(){ int i,j; int a,b,dis,mon; while(scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break; init(); for(i = 1; i <= m; i++) { scanf("%d %d %d %d",&a,&b,&dis,&mon); if(dis < mat[a][b]) { mat[a][b] = mat[b][a] = dis; cost[a][b] = cost[b][a]= mon; } if(dis == mat[a][b]) { if(mon < cost[a][b]) cost[a][b] = cost[b][a] = mon; } } int s, e; scanf("%d%d",&s,&e); int ans = dijkstra(s, e); printf("%d %d\n",ans,MONEY[e]); } return 0;}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

你可能感兴趣的文章
python 异常
查看>>
百度账号注销
查看>>
mysql-This version of MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME 错误解决
查看>>
BIEE Demo(RPD创建 + 分析 +仪表盘 )
查看>>
Cocos2dx 3.0开发环境的搭建--Eclipse建立在Android工程
查看>>
基本概念复习
查看>>
重构第10天:提取方法(Extract Method)
查看>>
Android Fragment使用(四) Toolbar使用及Fragment中的Toolbar处理
查看>>
解决pycharm在ubuntu下搜狗输入法一直固定在左下角的问题
查看>>
多线程day01
查看>>
react-native 模仿原生 实现下拉刷新/上拉加载更多(RefreshListView)
查看>>
MySQL出现Access denied for user ‘root’@’localhost’ (using password:YES)
查看>>
通过Roslyn构建自己的C#脚本(更新版)(转)
查看>>
红黑树
查看>>
UIImagePickerController拍照与摄像
查看>>
python调用windows api
查看>>
第四章 mybatis批量insert
查看>>
Java并发框架——什么是AQS框架
查看>>
【数据库】
查看>>
Win配置Apache+mod_wsgi+django环境+域名
查看>>