迪杰斯特拉&&优化 author：tc

发表于

勤劳的tc又来来了啊，这回是迪杰斯特拉啊，呃呃不会英文好难受。。sad。主要是不想学习。。。。
还是写博客舒服
Dijkstra
nice百度到了
eee 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
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

int mat[2510][2510];
int lenth[5000];
int maxn = 0x3f3f3f;
bool bj[2510];
int n;

void disk(int des) {
	int i = 0;
	memset(lenth,88,sizeof(lenth));
	for(i = 1; i <= n; i++)
		lenth[i] = mat[des][i];
	bj[des] = true;
	int sta = des;
	for(i = 1; i <= n; i++) {
		maxn = 0x3f3f3f;
		int j = 1;
		for(j; j <= n; j++)
			if(!bj[j] && maxn > lenth[j]) {
				maxn = lenth[j];
				sta = j;
			}
		bj[sta] = true;
	    j = 1;
		for(;j <= n;j++)
			lenth[j] = min(lenth[j],mat[sta][j] + lenth[sta]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	int m,s,t;
	cin >> n >> m >> s >> t;
	int i,j;
	memset(mat,maxn,sizeof(mat));
	int sub,sub1,value;
	for(i = 0; i < m; i++) {
		cin >> sub >> sub1 >> value;
		mat[sub][sub1] = value;
		mat[sub1][sub] = value;
	}
	disk(s);
	cout<<lenth[t];
	return 0;
}

可以看到，每回都要用循环更新源点到每个点之间最短值的最短值，这是很费时间的，所以这里我们可以用stl库里面的优先队列来优化，只取他的最大值。这里的还要用到greater/less greater是将小的放前面，从小到大排序stl默认好像是less。。。

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
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>


using namespace std;

typedef long long ll;

int mat[2510][2510];
int lenth[5000];
int maxn = 0x3f3f3f;
int n;
typedef pair<int,int> pa;

priority_queue<pa,vector<pa>,greater<pa> > rec;

void disk(int des) {
	int i = 0;
	pa p;
	memset(lenth,88,sizeof(lenth));
	for(i = 1; i <= n; i++) {
		lenth[i] = mat[des][i];
		rec.push(pa(mat[des][i],i));
	}
	int sta = des;
     while(!rec.empty())
     {
     	p = rec.top();
     	rec.pop();
     	int sub = p.first;
     	sta = p.second;
     	int j;
     	for(j = 1;j <= n;j++)
     	{
     		if(lenth[j] > lenth[sta] + mat[sta][j])
     		{
     			lenth[j] = lenth[sta] + mat[sta][j];
     			rec.push(pa(lenth[j],j));
			 }
		 }
	 }
}

int main() {
	ios::sync_with_stdio(false);
	int m,s,t;
	cin >> n >> m >> s >> t;
	int i,j;
	memset(mat,maxn,sizeof(mat));
	int sub,sub1,value;
	for(i = 0; i < m; i++) {
		cin >> sub >> sub1 >> value;
		mat[sub][sub1] = value;
		mat[sub1][sub] = value;
	}
	disk(s);
	cout<<lenth[t];
	return 0;
}