【id:593】【10分】E. 旅游规划

题目描述

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入

输入说明：输入数据的第1行给出4个正整数N、M、S、D，

其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N?1)；

M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。

随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入输出样例

输入样例1 <-复制
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20输出样例1
3 40

分析

输入输出样例过程如图所示，总的来说，就是运用迪杰斯特拉算法不断更新。

AC代码

#include 
#include 
#include
#define max 10000
using namespace std;int n, m, s, d;
int L[100][100];  //城市之间的距离
int F[100][100];  //城市之间的收费
int LL[100];      //到起点的最近距离
int FF[100];      //到起点的最近距离的收费
int flag[100];    //是否走过void Dijkstra()
{memset(flag, 0, sizeof(flag));//flag清零memset(LL, max, sizeof(LL));//LL清零LL[s] = 0;int k = n;while (k--){int x, min = max;for (int i = 0; i < n; i++){if (flag[i] == 0 && LL[i] < min)//flag==0确保每个点都会作为起始点来一遍{x = i;min = LL[i];}}flag[x] = 1; //标志这个点已经当过起始点for (int j = 0; j < n; j++)if (L[x][j] != 0&&flag[j]==0)//寻找与当前点相连的点且排除前面选过的点{int xinju = L[x][j] + LL[x];//新距离int xinfei = F[x][j] + FF[x];//新费用if (xinju < LL[j])//距离最短优先{LL[j] = xinju;FF[j] = xinfei;}else if (xinju == LL[j]){if (xinfei < FF[j]){FF[j] = xinfei;}}}}
}
int main()
{cin >> n >> m >> s >> d;memset(L, max, sizeof(L));//L初始为无穷大表示无连接while (m--){int a, b, l, f;cin >> a >> b >> l >> f;L[a][b] = l, L[b][a] = l;F[a][b] = f, F[b][a] = f;}Dijkstra();cout << LL[d] << " " << FF[d];
}

（by 归忆） 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！