有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式说明：
输入说明：输入数据的第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
3 40
2
2 1 0 1
1 0 2 3
2 3
本题是一个Dijkstra的变式应用题，思考难度个人觉得比较大。关键在于题目中说的，在路径都最短时输出花费最小的那个路径。就对原有的Dijkstra算法做了两点改动。都在找到最小边加入之后更新其他边时发生，一是当找到新加点的最短路径后，将路径和花费金钱都更新。二是若找到最短路径和原有的最短路径相同。那么只更新花费为小的那个即可。因为此题并没有要求输出最小的那个路径，所以在这一步里没有必要去做父亲结点数组。但如果要求输出路径，就需要再开一个数组做回朔了。
#include<cstdio>
#include<iostream>
#define INFINITY 100000
//#define LOCALtypedef struct {int length,cost;
}Point;Point G[505][505];using namespace std;int Dijkstra(int N,int star,int* D,int* C);int main(){
#ifdef LOCALfreopen("data.in","r",stdin);freopen("data.out","w",stdout);
#endifint N,M,S,D,city1,city2,Length,Cost;cin >> N >> M >> S >> D;int i,j;
// 初始化 for(i = 0;i<N;i++)for(j = 0;j<N;j++)G[i][j].length = G[i][j].cost = INFINITY;
// 读入一系列点 for(i = 0;i<M;i++){cin >> city1 >> city2 >> Length >> Cost;G[city1][city2].length = G[city2][city1].length = Length;G[city1][city2].cost = G[city2][city1].cost = Cost;}int MinDist[N],MinCost[N];Dijkstra(N,S,MinDist,MinCost);cout << MinDist[D] << " " << MinCost[D] ;return 0;
}int Dijkstra(int N,int star,int* D,int* C){int Final[505],j,i,minD,minV;
// 对起始点初始化 for(i = 0;i<N;i++){Final[i] = 0;D[i] = G[star][i].length;C[i] = G[star][i].cost;}
// 特殊点初始化 D[star] = 0;C[star] = 0;Final[star] = 1;for(j = 1;j<N;j++){minD = INFINITY;
// 查找最小边 for(i = 0;i<N;i++)if(!Final[i] && D[i]<minD){minV = i;minD = D[i];}
// 仅在此处访问边 if(minD < INFINITY)Final[minV] = 1;elsereturn -1;
// 边被访问后其他点做出更新 for(i = 0;i<N;i++)if( !Final[i] ){
// 如果有最短路，更新路径和花费 if(D[minV] + G[minV][i].length < D[i]){D[i] = D[minV] + G[minV][i].length;C[i] = C[minV] + G[minV][i].cost;}
// 如果出现相同最短路，更新为最小花费 else if(D[minV] + G[minV][i].length == D[i] && C[minV] + G[minV][i].cost < C[i])C[i] = C[minV] + G[minV][i].cost; }} return 0;
}
本文链接：https://my.lmcjl.com/post/6591.html
展开阅读全文
4 评论