一个人的旅行 【Dijkstra+堆优化】

题目链接HDU-2066


题目描述

虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。


思路

一开始看着是多源最短路,所以用Floyd算法搞了搞,然后交了一发TLE, 看到他的顶点数 <= 1000 所以n的复杂度必然会超时,所以有用Dijkstra+堆优化搞了一下;计算多次从指定出发点出发的最短路,每次取出最小的终点;双重循环就可以搞定;

易错:
1.给出的边是无向边;
2.可能y有重边

TLE代码 Floyd算法

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
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1010
#define INF 0x3f3f3f3f

int mat[MAX_N][MAX_N];

void init()
{
for(int i = 1; i<MAX_N; i++)
{
for(int j = 1; j<MAX_N; j++)
mat[i][j] = INF;
}
}

void Floyd(int n)
{
for(int k = 1; k<=n; k++)
{
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
if(mat[i][k] + mat[k][j] < mat[i][j])
mat[i][j] = mat[i][k] + mat[k][j];
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t, s, d;
int x, y, val;
while(cin >> t >> s >> d)
{
init();
int tmp_max = -INF;
for(int i = 1; i<=t; i++)
{
cin >> x >> y >> val;
tmp_max = max(tmp_max, max(x, y));
mat[x][y] = val;
}
Floyd(tmp_max);
vector<int> a, b;
for(int i = 1; i<=s; i++)
{
int tmp;
cin >> tmp;
a.push_back(tmp);
}
for(int i = 1; i<=d; i++)
{
int tmp;
cin >> tmp;
b.push_back(tmp);
}
int tmp_min = INF;
for(int i = 0; i<a.size(); i++)
{
for(int j = 0; j<b.size(); j++)
{
tmp_min = min(tmp_min, mat[a[i]][b[j]]);
}
}
cout <<tmp_min << endl;
}
return 0;
}

AC代码 Dijkstra + 堆优化算法

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

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1010
#define MAX_M 100010
#define INF 0x3f3f3f3f

int head[MAX_M], dist[MAX_N], vis[MAX_N], cnt = 0;

struct Node{
int to, val, next;
}edge[MAX_M];

struct Min_Heap{
int key, val;
bool operator < (const Min_Heap &a) const
{
return a.val < val;
}
Min_Heap(int tmp_key, int tmp_val)
{
key = tmp_key;
val = tmp_val;
}
};

void init(int n)
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++)
dist[i] = INF;
}

void add(int x, int y, int val)
{
edge[cnt].to = y;
edge[cnt].val = val;
edge[cnt].next = head[x];
head[x] = cnt++;
}

void Dijkstra(int n, int v)
{
priority_queue<Min_Heap> S;
dist[v] = 0;
S.push(Min_Heap(v, dist[v]));
while(!S.empty())
{
Min_Heap h = S.top();
S.pop();
if(vis[h.key])
continue;
vis[h.key] = 1;
for(int j = head[h.key]; j != -1; j = edge[j].next)
{
int v = edge[j].to;
if(!vis[v] && h.val + edge[j].val < dist[v])
{
dist[v] = h.val + edge[j].val;
S.push(Min_Heap(v, dist[v]));
}
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t, s, d;
while(cin >> t >> s >> d)
{
init(MAX_N-1);
int tmp_max = -INF;
for(int i = 1; i<=t; i++)
{
int x, y, val;
cin >> x >> y >> val;
tmp_max = max(tmp_max, max(x, y));
add(x, y, val);
add(y, x, val);
}
vector<int> a, b;
for(int i = 1; i<=s; i++)
{
int tmp;
cin >> tmp;
a.push_back(tmp);
}
for(int i = 1; i<=d; i++)
{
int tmp;
cin >> tmp;
b.push_back(tmp);
}
int tmp_min = INF;
for(int i = 0; i<a.size(); i++)
{
int v = a[i];
memset(vis, 0, sizeof(vis));
Dijkstra(tmp_max, v);
for(int j = 0; j<b.size(); j++)
{
tmp_min = min(tmp_min, dist[b[j]]);
}
}
cout << tmp_min << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------