PTA---7-9 旅游规划（Warshall算法，时间复杂度O(N³)）_pta旅游规划测试点

PTA数据结构与算法题目集—旅游规划

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

3 40
1

思路

1. 第一，很快要明白这是一道最短路径的题目，以学过的算法来看，可以用dfs,bfs,warshall,dijkstra等，
2. 第二，看到很多人都用了dijkstra算法，可能有些小伙伴不太清楚这个算法，这里我用较为简单的warshall算法(相信学过左孝凌的离散数学都知道这个算法)
3. 现在先来介绍下warshall算法吧

warshall算法<敲重点>

我们知道从A->B最简单的走法就是直接法…当然就是A->B咯，但是我们要求最短的！！！
所以可能A->B长度等于4，然而期间有一个K，使得A->K>B-等于3，这样，我们就将A->B更改数值为3，当然也存在A->K1->K2->B等于2的(当然这样的话我们就需要先把A->K2的最短路径算出来)，如此这样，我们就能求出A->B的最短路径了
所以我们可以很简单得到求一个K的代码了（先假设K = 1）

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(matrix[i][j] > matrix[i][k]+matrix[k][j])
matrix[i][j] = matrix[i][k]+matrix[k][j];
1
2
3
4

当然这样的K是从0-N-1的咯
所以外加一层循环
最终的终极代码就是

	for(k=0;k<n;k++)
	for(i=0;i<n;i++													)
	for(j=0;j<n;j++)
	if(a[i][j] > a[i][k]+a[k][j])
	a[i][j] = a[i][k]+a[k][j];
1
2
3
4
5

下面给出AC代码
(第一遍用dfs做的，下面的代码也没删…dfs最后一个测试点递归层次太多…超时了)

#include <stdio.h>
//算法问题，深度优先递归层次太多，导致超时
int n,m,s,d;
int book[2500];
int a[500][500];                    //长度
int b[500][500];                    //钱
int length=99999999,minmoney=999999999;                       //两个最小的
/*
//dfs
void dfs(int cur,int dis,int mon)
{
    if(dis > length || dis == length && mon > minmoney)
        return ;
    if(cur == d)
    {
        length = dis;
        minmoney = mon;
        return ;
    }
    
    for(int i=0;i<n;i++)
    {
        if(book[i] == 0 && a[cur][i] > 0)
        {
            book[i] = 1;
            dfs(i,dis+a[cur][i],mon+b[cur][i]);
            book[i] = 0;
        }
    }
    return ;
}
*/
//Warshall
void ini(int n)
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(i != j)
    a[i][j] = 10001,b[i][j] = 10001;
}
void print(int n)
{
	for(int i=0;i<n;i++)
	{	
		for(int j=0;j<n;j++)
		printf("%d ",a[i][j]);
		puts("");
	}
}
int main()
{
    //dfs
    /*
    scanf("%d %d %d %d",&n,&m,&s,&d);
    int i,j;
    for(i=0;i<m;i++)
    {
        int x,y,l,money;
        scanf("%d %d %d %d",&x,&y,&l,&money);
        a[x][y] = l;
        b[x][y] = money;
        a[y][x] = l;
        b[y][x] = money;
    }
    dfs(s,0,0);
    printf("%d %d",length,minmoney);
    return 0;
    */
    //Floyd-Warshall
    scanf("%d %d %d %d",&n,&m,&s,&d);
    int i,j;
    ini(n);
    for(i=0;i<m;i++)
    {
        int x,y,l,money;
        scanf("%d %d %d %d",&x,&y,&l,&money);
        a[x][y] = l;
        b[x][y] = money;
        a[y][x] = l;
        b[y][x] = money;
    }
    
	
    for(int k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        if(a[i][j] > a[i][k]+a[k][j] || a[i][j] == a[i][k]+a[k][j] && b[i][j] > b[i][k]+b[k][j])
            a[i][j] = a[i][k]+a[k][j],b[i][j] = b[i][k]+b[k][j];
    printf("%d %d\n",a[s][d],b[s][d]);
    
    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

------------------------------------------------------------------------------------end