博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【(图) 旅游规划 (25 分)】【Dijkstra算法】
阅读量:4966 次
发布时间:2019-06-12

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

1698539-20190921172256424-1796294815.png

#include
#include
#include
#include
using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;struct Road{ int _len; int _cost;}road[maxn][maxn];int vis[maxn];struct City{ int _len; int _cost;}d[maxn];int N, M, S, D;void init(){ for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) road[i][j]._len = INF, road[i][j]._cost = INF; for(int i = 0; i < N; i++) d[i]._len = INF, d[i]._cost = INF; d[S]._len = 0; d[S]._cost = 0;}void solve(){ memset(vis, 0, sizeof(vis)); for(int i = 1; i <= N; i++) { int x, minlen = INF; for(int j = 0; j < N; j++) { if(!vis[j] && d[j]._len < minlen) { minlen = d[j]._len; x = j; } } vis[x] = 1; if(minlen == INF) break; for(int y = 0; y < N; y++) { if(!vis[y]) { if(d[y]._len > d[x]._len + road[x][y]._len) { d[y]._len = d[x]._len + road[x][y]._len; d[y]._cost = d[x]._cost + road[x][y]._cost; } else if(d[y]._len == d[x]._len + road[x][y]._len) d[y]._cost = min(d[y]._cost, d[x]._cost + road[x][y]._cost); } } }}int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d %d %d %d", &N, &M, &S, &D); init(); int a, b, c, dd; for(int i = 0; i < M; i++) { scanf("%d %d %d %d", &a, &b, &c, &dd); road[a][b]._len = road[b][a]._len = c; road[a][b]._cost = road[b][a]._cost = dd; } solve(); printf("%d %d\n", d[D]._len, d[D]._cost);}

转载于:https://www.cnblogs.com/KeepZ/p/11563802.html

你可能感兴趣的文章
【Manthan, Codefest 18 (rated, Div. 1 + Div. 2) C】Equalize
查看>>
【codeforces 767A】Snacktower
查看>>
【MemSQL Start[c]UP 3.0 - Round 1 C】 Pie Rules
查看>>
Ognl中“%”、“#”、“$”详解
查看>>
我对应用软件——美团的看法
查看>>
执行了的程序,才是你的程序.
查看>>
struts2.x + Tiles2.x读取多个xml 配置文件
查看>>
表单校验之datatype
查看>>
python第六篇文件处理类型
查看>>
ubuntu16系统磁盘空间/dev/vda1占用满的问题
查看>>
grid网格布局
查看>>
JSP常用标签
查看>>
dashucoding记录2019.6.7
查看>>
九涯的第一次
查看>>
处理器管理与进程调度
查看>>
页面懒加载
查看>>
向量非零元素个数_向量范数详解+代码实现
查看>>
java if 用法详解_Java编程中的条件判断之if语句的用法详解
查看>>
java -f_java学习笔记(一)
查看>>
java 什么题目好做_用java做这些题目
查看>>