hdu 1874最短路

Posted on | In |

Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。

Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。

Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
 

Sample Output
2
-1

SPFA算法

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
#include<bits/stdc++.h>
#define INF 1e8
#define MAX 205
using namespace std;

int n,m;

struct node{
	int x;
	int v;
	node(int xx,int vv):x(xx),v(vv){
	}
};
vector<node> g[MAX];
int dis[MAX],isq[MAX];
void init(int n){
	for(int i=0;i<n;i++)
	g[i].clear();
	for(int i=0;i<n;i++)
	dis[i]=INF;	
	memset(isq,0,sizeof(isq));
	
	
}

int main(){
	int u,v,w;
	
	while(cin>>n>>m){
	queue<int> q;

	init(n);

	for(int i=0;i<m;i++){
			cin>>u>>v>>w;
			g[u].push_back(node(v,w));
			g[v].push_back(node(u,w));
	}
	int s,t;
	cin>>s>>t;
	q.push(s);
	isq[s]=1;
	dis[s]=0;
	while(!q.empty())	
	{
		int num=q.front();
		q.pop();
		isq[num]=0;
		for(int i=0;i<g[num].size();i++){
			int v=g[num][i].v;
			int x=g[num][i].x;
			if(dis[num]+v<dis[x]){
				dis[x]=dis[num]+v;
				if(isq[x]) continue;
				q.push(x);
				isq[x]=1;
			}
		}
		
		
		
		}
				
	
	
	if(dis[t]==INF) cout<<-1<<endl;
	else cout<<dis[t]<<endl;
	 
}
	
	
}

SPFA中取数字的方式有很多除了使用优先队列以外还有队列、数组、堆、栈等，总之它们的作用的就是不断的更新每个点到起点的路程。同时更新后又将它加入到队列/数组/堆/栈中。（需要注意如果是用队列优化则在加入队列前还需要判断它是否在队列中。）

参考
https://blog.csdn.net/ccutyear/article/details/53894625/53894625