发布于   更新于 题解 PAT 图 迪杰斯特拉

由于这道题对于我做 PAT 来说是第一次做带有算法的题，所以本次题解会多出来剖析，来分析局部代码和代码的整体思路，帮助自己能够更好的理解整道题，和迪杰斯特拉算法。

做 PAT 第一次遇到算法题，又让我想起了去年夏天被算法题支配的恐怖。

赶紧记下来。

题目

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input:

1
2
3
4
5
6
7
8
9
> 5 6 0 2
> 1 2 1 5 3
> 0 1 1
> 0 2 2
> 0 3 1
> 1 2 1
> 2 4 1
> 3 4 1
>

Sample Output:

1
2
> 2 4
>

中文翻译

第一行
N 城市的数量，城市被标号从0~n-1。
M 边数。
C1,C2 C1城->C2城。

第二行
包含N整数，第i个表示第i个城市救援队的数目。

m行
边的起始点，终点，边的权值。

目的：找出最短路中，能聚集最多救援人员的路

想法

这道题是一道典型的最短路问题，所以选择了迪杰斯特拉算法，并且在原有的算法基础上，新增了权值数组，来记录从起点到某一点的点权。当路径长度相同的时候，更新为权重较大的那一方即可。

本题做了三个多小时，才依靠着 题解 的帮助做完，证明自己还是比较菜的。

源代码

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
94
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>


using namespace std;
const int maxn = 505;
const int  INF = 1000000000;

int G[maxn][maxn]; //图
int d[maxn];  //起点到此点的距离
int vis[maxn]; //标记是否访问
int weight[maxn]; //点的权重
int w[maxn];  //到每个点的最短路径的累计权重
int num[maxn]; //到每个点的最短路径条数
int N, M, C1, C2;

void Dijkstra(int s)
{
	d[s] = 0;
	num[s] = 1;
	w[s] = weight[s];

	for (int i = 0; i < N; i++)
	{
		int u = -1;
		int MIN = INF;
		/*
			在所有的顶点中，找出来没有被访问的，且起点到此点距离最短的
		*/
		for (int j = 0; j < N; j++)
		{
			if (vis[j] == false && d[j] < MIN)
			{
				u = j;
				MIN = d[j];
			}
		}//end for j

		if (u == -1)return;//u之后没有路了

		vis[u] = true;//置u这个点被访问过了


		


		for (int v = 0; v < N; v++)
		{
			if (vis[v] == false && G[u][v] != INF)
			{
				if (d[u] + G[u][v] < d[v])//找出来u之后，离u距离最短的点v
				{
					d[v] = d[u] + G[u][v];//更新v到源点的距离
					w[v] = w[u] + weight[v];//更新v到源点的权重
					num[v] = num[u];//更新最短路径条数
				}
				else if (d[u] + G[u][v] == d[v])
				{
					num[v]+=num[u];//每个点不止被访问一次，在此之前这个点就被初始化过，
					if (w[u] + weight[v] > w[v])
					{
						w[v] = w[u] + weight[v];//路径长相同，保存权值较大的
					}
				}
			}
		}
	}


}

int main()
{
	int c1, c2, L;
	cin >> N >> M >> C1 >> C2;
	fill(d, d + maxn, INF);
	memset(vis, false, sizeof(vis));
	fill(G[0], G[0] + maxn * maxn, INF);
	for (int i = 0; i < N; i++)
	{
		cin >> weight[i];
	}
	for (int i = 0; i < M; i++)
	{
		cin >> c1 >> c2 >> L;
		G[c1][c2] = L;
		G[c2][c1] = L;

	}
	Dijkstra(C1);
	cout << num[C2] <<" "<< w[C2];
}

代码剖析

一. 首先从 main() 函数看起。

1
2
fill(d, d + maxn, INF);
memset(vis, false, sizeof(vis));

fill 函数和 memset 函数都是将某一块内存快速更改为同一内容的函数，但 memset 只能用在对于字符，串，和整型0、-1的填充， fill 函数可以用来填充整型变量。

二. Dijistra 函数。

  1. 初始化

    1
    2
    3
    d[s] = 0;
    num[s] = 1;
    w[s] = weight[s];

    这三行代码是对源点做处理：

    • 源点到自身的距离应当为0。
    • 通路数目至少为 1。
    • 刚开始时，累计权重即为自身的权重。

  2. for 循环 n 次

    1. 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      int u = -1;
      		int MIN = INF;
      		/*
      			在所有的顶点中，找出来没有被访问的，
      			且起点到此点距离最短的
      		*/
      		for (int j = 0; j < N; j++)
      		{
      			if (vis[j] == false && d[j] < MIN)
      			{
      				u = j;
      				MIN = d[j];
      			}
      		}//end for j

      		if (u == -1)return;//u之后没有路了

      这 16 行代码的目的时为了找到在所有的顶点中，使d[u]最小且还未被访问的顶点的标号。

      1. 以第 u 点为基准，向后搜索 v $0$—v${n-1}​$ 的点

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        if (d[u] + G[u][v] < d[v])//找出来u之后，离u距离最短的点v
        {
        	d[v] = d[u] + G[u][v];//更新v到源点的距离
        	w[v] = w[u] + weight[v];//更新v到源点的权重
        	num[v] = num[u];//更新最短路径条数
        }
        else if (d[u] + G[u][v] == d[v])
        {
        	num[v]+=num[u];//每个点不止被访问一次，在此之前这个点就被初始化过，
        	if (w[u] + weight[v] > w[v])
        	{
        		w[v] = w[u] + weight[v];//路径长相同，保存权值较大的
        	}
        }

        这十五行代码中的 if - else 结构是必不可少的。如果去掉了 else 语句，函数会在第 7 行陷入死循环。

        参考链接：https://blog.csdn.net/qq_26398495/article/details/81606309

    Dijstra 算法伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    > //G为图，一般设为全局变量，数组d为源点到达各个点的最短路径长度，s为起点
    > Dijkstra(G, d[], s) {
    >     初始化;
    >     for(循环n次) {
    >         u = 使d[u]最小且还未被访问的顶点的标号;  //暴力搜索 or 堆结构
    >         标记u已被访问;
    >         for(从u出发能到达的所有顶点v) {
    >             if (v未被访问 && 以u为中介点 使 s到顶点v的最短距离d[v]更优) {
    >                 优化d[v];
    > 	            //可以在此处保存路径 把u保存为v的前驱即可
    > 	            pre[v] = u;
    >             }
    >         }
    >     }//for
    > }//Dijkstra
    >

    实现差异： 主要区别主要在于如何枚举从u出发到达的顶点v上；邻接矩阵需要枚举所有结点查看顶点v能否到达u，而邻接表则可以直接得到这些顶点v；

    注： 若题目所给为无向图，把它转化为两条有向边即可！

    代码举例

    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
    > int G[maxn][maxn]; //顶点数，图
    > 
    > //邻接矩阵版本
    > void Dijkstra(int s) {
    >     fill(d, d + maxn, INF); //初始为不可达(慎用memset)
    >     d[s] = 0;
    >     
    >     for(int i = 0; i < n; i++) { //循环n次(第一次找到的肯定是起点本身，正好完成初始化)
    > 
    > 	     //找到未访问结点中d[]最小的 
    >         int u = -1, MIN = INF;
    >         for(int j = 0; j < n; j++) {
    >             if(vis[j] == false && d[j] < MIN) {
    >                 u = j;
    >                 MIN = d[j];
    >             }
    >         }
    > 
    >         if(u == -1)  //找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
    >             return;
    > 
    >         vis[u] = true; //标记已访问
    >         for(int v = 0; v < n; v++) { //更新
    >             //如果v未访问 && u能到达v && 以u为中介点可以是d[v]更优
    >             if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
    >                 d[v] = G[u][v] + d[u];
    > 	            pre[v] = u;
    >             }
    >         }
    > 
    >     }//for - i
    > }//Dijkstra
    > 
    > //时间复杂度：两层循环 ,O(n^2)
    >

    常考题型

    题目考法
    很多时候最短路径不止一条，就需要题目所给的其他条件选择其中一条；一般有一下三种考法：

    1. 给每条边再增加一个边权（比如花费），然后要求最短路径有多条时，选择花费之和最小的；
    2. 给每个点增加一个点权，有多条最短路径时，选择点权之和最大（最小）的；
    3. 直接问有多少条最短路径；

    这三种出法都只需增加一个数组，存放新增的边权或点权或最短路径条数然后在Dijkstra()中修改 更新d[v] 的那一步操作即可；其他无需改变；

参考

作者：3stone_
原文：

相关文章
评论
分享
返回顶部
Please check the post_relate setting in config.yml of hexo-theme-Annie! You should make sure 'postsEnable == true' and the number of site posts greater than 1.
Please check the comment setting in config.yml of hexo-theme-Annie!