1 #include<stdio.h>
2 #include<
string.h>
3 #include<iostream>
4 #include<queue>
5 #include<vector>
6 using namespace std;
7
8 const int INF =
0x3f3f3f3f;
9 const int MAX =
10000;
10
11 struct edge
12 {
13 int to,w;
14 };
15 int n,m;
16 int inque[MAX+
10];
//标记节点是否在队列里
17 int dis[MAX+
10];
//保存最短路径
18 int vexcnt[MAX+
10];
//保存节点进队次数
19 vector<edge>map[MAX+
10];
20
21 bool spfa(
int s)
22 {
23 queue<
int>
que;
24 memset(inque,
0,
sizeof(inque));
25 memset(vexcnt,
0,
sizeof(vexcnt));
26 //初始化
27 for(
int i =
1; i <= n; i++
)
28 dis[i] =
INF;
29 dis[s] =
0;
30
31 que.push(s);
32 inque[s] =
1;
33 vexcnt[s]++
;
34 while(!
que.empty())
35 {
36 int u =
que.front();
37 que.pop();
38 inque[u] =
0;
39 for(
int i =
0; i < map[u].size(); i++
)
40 {
41 int to =
map[u][i].to;
42 if(dis[u] > INF && dis[to] > map[u][i].w +
dis[u] )
43 {
44 dis[to] = map[u][i].w +
dis[u];
45 if(inque[to] ==
0)
46 {
47 que.push(to);
48 inque[to] =
1;
49 vexcnt[to]++
;
50 if(vexcnt[to] >= n)
//进队超过n次说明出现负环
51 return false;
52 }
53 }
54 }
55 }
56 return true;
57 }
58
59 int main()
60 {
61 int u,v,w,s,t;
62 while(~scanf(
"%d %d",&n,&
m))
63 {
64 scanf(
"%d %d",&s,&
t);
65 for(
int i =
1; i <= n; i++
)
66 map[i].clear();
//清空
67 for(
int i =
1; i <= m; i++
)
68 {
69 scanf(
"%d %d %d",&u,&v,&
w);
70 map[u].push_back((
struct edge){v, w});
//把v接到u的后面
71 }
72 spfa(s);
73 printf(
"%d\n",dis[t]);
74 }
75 return 0;
76 }
View Code
1 int map[
100][
100];
2 int dis[
100];
3 int inque[
100];
4 int vexcnt[
100];
5 bool spfa(
int s)
6 {
7 queue<
int>
que;
8 memset(inque,
0,
sizeof(inque));
9 memset(vexcnt,
0,
sizeof(vexcnt));
10 //初始化
11 for(
int i =
1; i <= n; i++
)
12 dis[i] =
INF;
13 dis[s] =
0;
14
15 que.push(s);
//开始将源点进队列
16 inque[s] =
1;
//标记
17 vexcnt[s]++;
//进队次数加1
18 //每次从队列中取出一个元素,并对所有与它相邻的点松弛,
19 //若某个相邻的点松弛成功则将其入队,直到队列为空结束,
20 while(!
que.empty())
21 {
22 int u =
que.front();
23 que.pop();
24 inque[u] =
0;
25 for(
int i =
1; i <= n; i++
)
26 {
27 if(dis[u] < INF && dis[i] > dis[u] +
map[u][i])
28 dis[i] = dis[u] +
map[u][i];
29 if(!
inque[i])
30 {
31 queue.push(i);
32 inque[i] =
1;
33 vexcnt[i]++
;
34 if(vexcnt[i] >= n)
//若某节点入队超过n次说明出现负权
35 return false;
36 }
37 }
38
39 }
40 return true;
41 }
View Code
spfa中如果节点v入队超过n次,即vexcnt[v] > n,说明有负环,就退出。而不是vexcnt[v] >= n;
转载于:https://www.cnblogs.com/LK1994/p/3228308.html
相关资源:JAVA上百实例源码以及开源项目