PTA旅游规划_pta 7-12 旅游规划

链接: 题目

介绍两种做法做这道题
第一种做法 也就是纯迪杰斯特拉算法，也就是复杂度为O(N*N)时间复杂度的做法。采用邻接矩阵存图+迪杰斯特拉算法。

第二种做法。 优先队列优化的迪杰斯特拉算法，时间复杂度是mlog(N)。采用邻接表+优先队列+迪杰斯特拉算法。

两种做法适用的领域不一样，而且这道题好像第一种更适合，因为图比较小，而且我的代码提交评测耗时让我很意外。按理说的第二种优化的应该更快的，但是实际第一种比第二种快100多ms。可能是存图上的差异带来的。第一种更适合做小图，第二种适合做大图。

原题:

第一种做法
第一种做法最大耗时128ms。

第二种做法
优先队列优化的耗时209ms，说实话很让我感到意外。

话不多说直接上代码了，希望大家多多支持我这个小菜鸟

第一种做法

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 505;
int n,m,s,d;
int map[maxn][maxn];				//权重 
int visited[maxn];					//标记 
int a[maxn][maxn];					//路费 
int cost[maxn];						//花费 
int dist[maxn];						//距离 
void dijkstra()
{
	dist[s] = 0;
	cost[s] = 0;
	while(1){
		int min = 10000, k = -1;
		for(int i = 0;i < n;i++){
			if(dist[i] < min && visited[i] == 0){
				min = dist[i];
				k = i;
			}
		}
		if(k == -1){
			break;
		}
		visited[k] = 1;
		for(int i = 0;i < n;i++){
			if(visited[i] == 0){
				if(dist[i] > dist[k] + map[k][i]){
					dist[i] = dist[k] + map[k][i];
					cost[i] = cost[k] + a[k][i];
				}
				else if(dist[i] == dist[k] + map[k][i]){
					if(cost[i] > cost[k] + a[k][i]){
						cost[i] = cost[k] + a[k][i];
					}
				}
			} 
		}
	}
} 
int main()
{
    while(cin>>n>>m>>s>>d){
        int x,y,l,p;
        for(int i = 0;i < n;i++){
        	for(int j = 0;j < n;j++){
        		if(i!=j){
        			map[i][j] = 1000;
        			a[i][j] = 1000;
				}
			}
		}
        for(int i = 0;i < maxn;i++){
        	dist[i] = 1000;
        	visited[i] = 0;
        	cost[i] = 1000;
		} 
        for(int i = 0;i < m;i++){
            cin>>x>>y>>l>>p;
            map[x][y] = map[y][x] = l;
            a[x][y] = a[y][x] = p;
        }
		dijkstra();
		cout<<dist[d]<<" "<<cost[d]<<endl;
    }
    return 0;
}



第二种做法
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10005;
const int inf = 1e6;
int n,m,s,d;
struct edge{
    int from,to,w,price;
    edge(int a,int b,int c,int d){from = a;to = b; w = c;price = d;}
};
struct Node{
    int k,dis,cost;
    Node(int k1,int dis1,int cost1){k = k1;dis = dis1;cost = cost1;}
    bool operator < (const Node &a) const {
        if(dis == a.dis){                   //路径相等费用小的优先
            return cost > a.cost;
        }
        else{                               //路径小的优先
            return dis > a.dis;
        }
    }
};
priority_queue<Node>q;                      //优先队列
vector<edge>e[maxn];
void Dijkstra()
{
    while(!q.empty()){
        q.pop();
    }
    int dist[n+5],cost[n+5],visit[n+5];
    for(int i = 0;i < n;i++){
        dist[i] = cost[i] = inf;
        visit[i] = 0;
    }
    dist[s] = cost[s] = 0;
    q.push(Node(s,dist[0],cost[0]));
    while(!q.empty()){
        Node p = q.top();
        q.pop();
        if(visit[p.k]){
            continue;
        }
        visit[p.k] = 1;
        for(int i = 0;i < e[p.k].size();i++){
            edge t = e[p.k][i];
            if(visit[t.to] == 0){
                if(dist[t.to] > dist[p.k] + t.w){
                    dist[t.to] = dist[p.k] + t.w;
                    cost[t.to] = cost[p.k] + t.price;
                    q.push(Node(t.to,dist[t.to],cost[t.to]));
                }
                else if(dist[t.to] == dist[p.k] + t.w){
                    if(cost[t.to] > cost[p.k] + t.price){
                        dist[t.to] = dist[p.k] + t.w;
                        cost[t.to] = cost[p.k] + t.price;
                        q.push(Node(t.to,dist[t.to],cost[t.to]));
                    }
                }
            }
        }
    }
    printf("%d %d\n",dist[d],cost[d]);
}
int main()
{
    while(cin>>n>>m>>s>>d){
        for(int i = 0;i < n;i++){
            e[i].clear();
        }
        for(int i = 0;i < m;i++){
            int x,y,l,p;
            cin>>x>>y>>l>>p;
            e[x].push_back(edge(x,y,l,p));
            e[y].push_back(edge(y,x,l,p));
        }
        Dijkstra();
    }
    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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160