PTA 最短路径（Dijkstra和Floyd算法）_最短路径(迪杰斯特拉算法)pta

最短路径问题实际上就是在图中储存好每个点到别的点的最小距离，单源（单起点）问题往往用数组存放，多源问题常用邻接矩阵来处理。

多源问题常用Floyd算法来做，Floyd的核心是：当前I 到J的最小距离为I 到一小部分顶点 再到J的最小距离。然后不断的把K个顶点加到那一小部分顶点的集合中。直到K等于总顶点数N-1，就是整个图的实际多源距离。

例题：
07-图4 哈利·波特的考试 (25分)
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。

现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。

输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70

**思路：**实际上就是找图中每行的最大距离，然后将这N个最大距离做比较找出最小的那个值，输出对应的I，和最小的距离。看到多源图，考虑用Floyd算法。

需要注意的是：
1.给图里面填入边的时候，for循环的 I 和 J 都是从1开始的，直到累加到=<N 才结束。（因为编号是从1开始的），这个地方没注意导致卡了好久。
2.为了表示正无穷，一开始使用了标准库的<limit.h>中的 INT_ MAX来表示，最后发现经过运算后矩阵中会出现很多负数，原因是这个方法等于说是一个表达式，已经是最大的数字了，再进行运算很有可能溢出。故改用自己定义的MAXMAX来表示。

#include <iostream>
#include <stdio.h>

using namespace std;


const int MAXMAX = 100000;
const int Maxsize = 101;
int Graph[Maxsize][Maxsize];  //邻接矩阵

int BulidGraph()
{
   	
	int N, M;
	cin >> N>> M;

	for(int i = 0 ;i<=N;i++)
		for (int j = 0; j <= N; j++)
		{
   
			if (i == j)
				Graph[i][j] = 0; //对角线初始化
			else
				Graph[i][j] = MAXMAX; //没边 为正无穷
		}


	int i, j,weight;
	for (int a = 0; a < M; a++)
	{
   
		cin >> i>>j>> weight;
		Graph[i][j] = weight;
		Graph[j][i] = weight;
	}
	return N;
}

void Floyd(int N)//Floyd算法
{
   
	for (int k = 1; k <=  N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (Graph[i][k] + Graph[k][j] < Graph[i][j])
					Graph[i][j] = Graph[i][k] + Graph[k][j];//更新距离
}

int main() 
{
   
	int N;
	N = BulidGraph();

	Floyd(N);

	int Index = 0;
	int flag = 0;//是否有不连通的情况出现（此时max为正无穷）
	int Max;
	int Min = MAXMAX;
	for (int i = 1; i <= N; i++) 
	{
   
		Max = 0;
		for (int j = 1; j <= N; j++)
		{
   
			if (Graph[i][j] > Max)
				Max = Graph[i][j];
		}
		if (Min > Max) //如果min比当前i对应的最长边还要大
		{
   
			Index = i;
			Min = Max;//更新min

		}
		if (Max == MAXMAX)
			flag = 1; //确实有不连通的节点出现
	}

	//输出
	if (flag == 1)
		cout << 0;
	else
		cout << Index<<" " << Min;
	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

例二
07-图5 Saving James Bond - Hard Version (30分)
This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10
Sample Output 1:
4
0 11
10 21
10 35
Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
0

思路：让你找到可以跳跃的路线，并选择跳跃次数最小的一条路。如果次数相同，则选择第一次跳跃距离最小的那条线路。输出跳跃次数，和中间经过的所有节点的坐标。
我是用单源最短路径的方法做的，事实上网上有用Dijkstra做的，似乎更简单。

用起点(0,0)点作为起点，算出可以跳出的节点并组成集合。再在这个集合中找寻对起点来说最短跳跃次数的点。然后放入堆栈，倒序输出Path。（需要注意的是，堆栈的最上层是起点(0,0)，需要手动pop掉它，因为输出要求中不要写起点的坐标）。

易错点：
1.因为我在结构体中塞了一个vector分别存放每个点的邻接点的脚标。所以相当于是在数组中存放的结构体中包含动态的子结构。所以不能使用malloc。故使用new来申请内存。

new开辟的空间在堆上，而一般声明的变量存放在栈上。通常来说，当在局部函数中new出一段新的空间，该段空间在局部函数调用结束后仍然能够使用，可以用来向主函数传递参数。另外需要注意的是，new的使用格式，new出来的是一段空间的首地址。所以一般需要用指针来存放这段地址。

2.注意输出格式，上面有提到，堆栈的默认的top元素包含了起点，而这是不需要打印的。

3.vector.erase()，删一个位置，它这个位置自动释放，然后后面的元素全部顶到前面来。等于说size和后面的编号同时变化了。所以不要遍历删除。 最后我用了复制来解决这个问题。
vector.erase()用法：vector.erase (vecto