「codevs1557」Dijkstra

发表于 | 分类于

题目链接

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入描述 Input Description

第一行: 4个由空格隔开的整数:T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数:Rs, Re和Ci

输出描述 Output Description

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

样例输入 Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

样例输出 Sample Output

1
7

数据范围及提示 Data Size &

1
2
Hint
5->6->1->4 (3 + 1 + 3)

本题是一道单源最短路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
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 2500 + 5;
const int MAXM = 12400 + 5;
const int inf = 0x3f3f3f3;
int head[MAXN], dist[MAXN],  n, m, num, start, end;
//head数组记录存的是在这条边被加入之前的最后一条边（边表的一端）；
//dist数组储存起点到这个点的距离
struct Edge{
	int from, to, next, w;
}edge[MAXM];
//用于建图
inline int add_edge(int from, int to, int w) {
	edge[++num].from = from;
	edge[num].to = to;
	edge[num].w = w;
	edge[num].next = head[from];
    //next存上一条边（整条边）
	head[from] = num;
}
struct Dist {
	int x, dist;
	Dist(int x = 0, int dist = inf) : x(x), dist(dist) {}
    //结构体初始化
	bool operator () (Dist l, Dist r) {
		return l.dist > r.dist;
	}
    //重载运算符：按从小到大排序；
};
priority_queue <Dist, vector<Dist>, Dist> que;
//建立一个以Dist为元素的不定长数组；
int dijkstra() {
	for(int i = 1; i <= n; i++) dist[i] = inf;
	dist[start] = 0;
	que.push(Dist(start, 0));
    //初始化操作；
	while(!que.empty()) {
    //while(!que.empty())  如果队列为空返回一  取非之后返回零；也就是说当队列不为空时；
		Dist tmp = que.top();
		que.pop();
		if(tmp.dist != dist[tmp.x]) continue;
       //因为队列里面的数是不断更新的，如果不等于，说明这个点比较旧了，然而我们需要的其实是最新的点，所以就把它continue掉；
		for(int j = head[tmp.x]; j; j = edge[j].next) {
			if(dist[edge[j].to] > dist[tmp.x] + edge[j].w) {
				dist[edge[j].to] = dist[tmp.x] + edge[j].w;
				que.push(Dist(edge[j].to, dist[edge[j].to]));
			}
		}
        //遍历求距；
	}
	return dist[end];
}
int main() {
	scanf("%d%d%d%d", &n, &m, &start, &end);
	for(int j = 1; j <= m; j++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add_edge(x, y, z);
		add_edge(y, x, z);
	}
	printf("%d", dijkstra());
	return 0;
}