PTA 7-9 旅游规划 (25分)_有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路

作者：盐析白兔 | 2024-05-03 20:22:04

踩

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路

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

输入格式:

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

输出格式:

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

输入样例:

输出样例:

3 40
1

算法分析

**分析：**显然，这并非简单的dijkstratra算法（dijkstratra算法详见此处（文末代码由此改成）），因为这里涉及到了两个权值，我们优先比较距离的远近，距离相同则选择价钱低的。
在掌握了dijkstra算法之后我们看看这道题需要在哪些地方做出改变

核心代码分析：
1.注意城市的编号为 $0 - (N - 1)$ ；我们要注意在生成图时的边界条件。
2.产生有两个权值的图。

1）图的产生

for(i=0;i<vertex_num;i++)
    {
        for(j=0;j<vertex_num;j++)
         map[i][j] = INF;
         price[i][j] = INF;//注意第二个权值也要初始化
    }
1
2
3
4
5
6

 for(k=0;k<edge_num;k++)
    {
        scanf("%d%d",&i,&j);
        scanf("%d%d",&map[i][j],&price[i][j]);
        map[j][i] = map[i][j];
        price[j][i] = price[i][j];//两个权值都是无向图形式
    }
1
2
3
4
5
6
7

下面是完整的图的产生代码

void gen(int map[SIZE][SIZE],int price[SIZE][SIZE],int vertex_num,int edge_num)
{
    int i,j;
    int k;
    int Ver;
    int start,end;
    
    for(i=0;i<vertex_num;i++)
    {
        for(j=0;j<vertex_num;j++)
         map[i][j] = INF;
         price[i][j] = INF;
    }

    for(k=0;k<edge_num;k++)
    {
        scanf("%d%d",&i,&j);
        scanf("%d%d",&map[i][j],&price[i][j]);
        map[j][i] = map[i][j];
        price[j][i] = price[i][j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2）dijkstra算法

 for(i = 0 ; i < n  ; i ++){	//初始化 
        visit[i] = 0;	//一开始每个点都没被访问 
        len[i] = map[from][i];	//先假设源点到其他点的距离 
        cost[i] = price[from][i];//第二个权值的初始化
    }  
1
2
3
4
5

 for(j = 0 ; j < n ; ++j){
            if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
            { //如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  
                len[j] = len[pos] + map[pos][j];	//更新j节点到源节点的最短路径
                cost[j] = cost[pos] + price[pos][j];//同时更新最少消费
                parent[j]=pos;	//记录前驱结点
            }  
            else if((!visit[j] )&& (len[j] == (len[pos] +map[pos][j]))&&(cost[j] > cost[pos] + price[pos][j] ))//当发现有距离相同时及时更新价钱为较少的一条路的价钱(虽然此题就具体路径并未考察)
            {
                cost[j] = cost[pos] + price[pos][j];
                parent[j] = pos;//同时记录下前驱节点，记录下这条价钱较少的路的轨迹(虽然此题就具体路径并未考察)
            }
        }  
1
2
3
4
5
6
7
8
9
10
11
12
13

下面是dijkstra算法的核心函数

int dijkstra(int from, int to,int map[SIZE][SIZE],int price[SIZE][SIZE],int n,int m){	//从源点到目标点 
	
    int i,j;  
    int START =from;
    int parent[SIZE];
    int cost[SIZE];
    int len[SIZE];  	//d[i]表示源点到i这个点的距离 
    int visit[SIZE];  //节点是否被访问 
    for(int i =0;i<SIZE;i++)
       parent[i]=START;
    
    for(i = 0 ; i < n  ; i ++){	//初始化 
        visit[i] = 0;	//一开始每个点都没被访问 
        len[i] = map[from][i];	//先假设源点到其他点的距离 
        cost[i] = price[from][i];
    }  
   
    for(i = 0 ; i < n ; ++i){	//对除源点的每一个点进行最短计算 
        int min = INF;  //记录最小len[i] 
        int pos;  //记录小len[i] 的点 
  
        for(j = 0 ; j < n ; ++j)
        {	
            if(!visit[j] && min > len[j]){  
                pos = j;  
                min = len[j];  
            }  
        }  
        visit[pos] = 1;  
  
        for(j = 0 ; j < n ; ++j){
            if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
            { //如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  
                len[j] = len[pos] + map[pos][j];	//更新j节点到源节点的最短路径
                cost[j] = cost[pos] + price[pos][j];
                parent[j]=pos;	//记录前驱结点
            }  
            else if((!visit[j] )&& (len[j] == (len[pos] +map[pos][j]))&&(cost[j] > cost[pos] + price[pos][j] ))
            {
                cost[j] = cost[pos] + price[pos][j];
                parent[j] = pos;
            }
        }  
    }  
    printf("%d %d",len[to],cost[to]);
  
    return len[to];
}
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

最后奉上完整代码！

#include<stdio.h>
  
#define SIZE 510  
#define INF 10000000
  
 
int dijkstra(int from, int to,int map[SIZE][SIZE],int price[SIZE][SIZE],int n,int m){	//从源点到目标点 
	
    int i,j;  
    int START =from;
    int parent[SIZE];
    int cost[SIZE];
    int len[SIZE];  	//d[i]表示源点到i这个点的距离 
    int visit[SIZE];  //节点是否被访问 
    for(int i =0;i<SIZE;i++)
       parent[i]=START;
    
    for(i = 0 ; i < n  ; i ++){	//初始化 
        visit[i] = 0;	//一开始每个点都没被访问 
        len[i] = map[from][i];	//先假设源点到其他点的距离 
        cost[i] = price[from][i];
    }  
   
    for(i = 0 ; i < n ; ++i){	//对除源点的每一个点进行最短计算 
        int min = INF;  //记录最小len[i] 
        int pos;  //记录小len[i] 的点 
  
        for(j = 0 ; j < n ; ++j)
        {	
            if(!visit[j] && min > len[j]){  
                pos = j;  
                min = len[j];  
            }  
        }  
        visit[pos] = 1;  
  
        for(j = 0 ; j < n ; ++j){
            if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
            { //如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  
                len[j] = len[pos] + map[pos][j];	//更新j节点到源节点的最短路径
                cost[j] = cost[pos] + price[pos][j];
                parent[j]=pos;	//记录前驱结点
            }  
            else if((!visit[j] )&& (len[j] == (len[pos] +map[pos][j]))&&(cost[j] > cost[pos] + price[pos][j] ))
            {
                cost[j] = cost[pos] + price[pos][j];
                parent[j] = pos;
            }
        }  
    }  
    printf("%d %d",len[to],cost[to]);
  
    return len[to];
}
void gen(int map[SIZE][SIZE],int price[SIZE][SIZE],int vertex_num,int edge_num)
{
    int i,j;
    int k;
    int Ver;
    int start,end;
    
    for(i=0;i<vertex_num;i++)
    {
        for(j=0;j<vertex_num;j++)
         map[i][j] = INF;
         price[i][j] = INF;
    }

    for(k=0;k<edge_num;k++)
    {
        scanf("%d%d",&i,&j);
        scanf("%d%d",&map[i][j],&price[i][j]);
        map[j][i] = map[i][j];
        price[j][i] = price[i][j];
    }
}
  
int main () {  
 
    int map[SIZE][SIZE]; 
    int price[SIZE][SIZE];
    int vertex_num; 
    int edge_num;
    int start,end;
    scanf("%d%d",&vertex_num,&edge_num);
    scanf("%d%d",&start,&end);
    gen(map,price,vertex_num,edge_num);

    dijkstra(start,end,map,price,vertex_num,edge_num);

    return 0;  
}

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
89
90
91
92
93

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/531358