Scott's world.

旅游规划

Word count: 835Reading time: 4 min
2019/08/21 Share

旅游规划

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

输入格式:

输入说明:输入数据的第1行给出4个正整数NMSD,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。

输出格式:

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

输入样例:

1
2
3
4
5
6
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

题目分析

  • 这道题就是dijkstra算法的变形

    除了需要判断最短路径时的权值,还需要判断最少路费时的权值,相当于要在判断时多加一个判断,并且更新其最短路径

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#define inf 1000001
#define Max 501
using namespace std;


int FindMinDist(vector<int> dist,vector<int> collected)
{
int N=dist.size();
int minDist=inf,V=-1;

for(int i=0;i<N;i++){
if(!collected[i]&&dist[i]<minDist){
minDist=dist[i];
V=i;
}
}
return V;
}

void dijkstra(int s,int d,vector<vector<int> >roadLen,vector<vector<int> >roadCost)
{
int N=roadLen[0].size();
vector<int> collected(N,false);
vector<int> path(N,-1);
vector<int> dist(N,0);
vector<int> cost(N,0);
//初始化最短路径数组
for (int i=0;i<N;i++){
//若没有邻接边则将其设为最大值
if(!roadLen[s][i]){
dist[i]=cost[i]=inf;
}else{
dist[i]=roadLen[s][i];
cost[i]=roadCost[s][i];
}
}

//将起始点S放到集合中
dist[s]=0;
collected[s]=true;

while(1){
//首先找到MinDist且未收录的顶点
int v=FindMinDist(dist,collected);
//若不存在则退出循环
if(v==-1){
break;
}
collected[v]=true;
for(int w=0;w<N;++w){
//V中没有被收录的邻接顶点
if(!collected[w]&&roadLen[v][w]){
if(dist[v]+roadLen[v][w]<dist[w]){
dist[w]=dist[v]+roadLen[v][w];
cost[w]=cost[v]+roadCost[v][w];
path[w]=v;
}else if(dist[v]+roadLen[v][w]==dist[w]&&
cost[v]+roadCost[v][w]<cost[w]){
cost[w]=cost[v]+roadCost[v][w];
}
}
}
}
cout<<dist[d]<<" "<<cost[d]<<endl;
}

int main()
{
int N,M,S,D;
cin>>N>>M>>S>>D;
vector<vector<int> >roadLen(N,vector<int>(N,0)),roadCost(N,vector<int>(N,0));
for(int i=0;i<M;i++){
int beg,ed,len,cost;
cin>>beg>>ed>>len>>cost;
roadLen[beg][ed]=len;
roadLen[ed][beg]=len;
roadCost[beg][ed]=cost;
roadCost[ed][beg]=cost;
}
dijkstra(S,D,roadLen,roadCost);
return 0;
}
CATALOG
  1. 1. 旅游规划
    1. 1.0.1. 输入格式:
    2. 1.0.2. 输出格式:
    3. 1.0.3. 输入样例:
    4. 1.0.4. 输出样例:
  2. 1.1. 题目分析
  3. 1.2. 答案