HDOJ 1874 【FLoyd】【Bellman】【Dijkstra】畅通工程续

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=1874



思路

单源单终点求最短路，有很多写法…数据小。
P.S.用floyd是有坑的，数据会给出一条起点和终点相同的正边，就会WA。



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
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max = 210000;
int dis[300][300];
int main()
{
	int n, m, a, b, s, t, x;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 0; i <= n + 1; i++)
			for (int j = 0; j <= n + 1; j++)
			{
				if (i == j) dis[i][i] = 0;
				else dis[i][j] = Max;
			}
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &a, &b, &x);
			a++; b++;
			if (dis[a][b]>x) dis[a][b] = dis[b][a] = x;
		}
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		scanf("%d%d", &s, &t);
		if (dis[s + 1][t + 1] == Max) printf("%d\n", -1);
		else printf("%d\n", dis[s + 1][t + 1]);
	}
	return 0;
}






Bellman_Ford：

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max = 2100000;
int dis[300];
struct data
{
	int from, to, value;
}edge[22000];
void Bellman_Ford(int n, int m, int s, int t)
{
	for (int i = 0; i<300; i++) dis[i] = Max;
	dis[s] = 0;
	for (int i = 0; i<n; i++)
		for (int j = 1; j <= m; j++)
		{
			dis[edge[j].to] = min(dis[edge[j].to], dis[edge[j].from] + edge[j].value);
		}
}
int main()
{
	int n, m, s, t;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].value);
			edge[i + m].to = edge[i].from;
			edge[i + m].from = edge[i].to;
			edge[i + m].value = edge[i].value;
		}
		scanf("%d%d", &s, &t);
		Bellman_Ford(n, m << 1, s, t);
		if (dis[t] == Max) printf("-1\n");
		else printf("%d\n", dis[t]);
	}
	return 0;
}

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max = 210000;
int dis[300], vis[300], Map[300][300];
void dijkstra(int n, int m, int s, int t)
{
	for (int i = 0; i<300; i++) dis[i] = Max;
	for (int i = 0; i<300; i++) vis[i] = 0;
	dis[s] = 0;
	while (1)
	{
		int v = -1;
		for (int i = 1; i <= n; i++)
			if (!vis[i] && (v == -1 || dis[i]<dis[v])) v = i;
		if (v == -1) break;
		vis[v] = 1;
		for (int i = 1; i <= n; i++)
			dis[i] = min(dis[i], dis[v] + Map[v][i]);
	}
}
int main()
{
	int a, b, x, n, m, s, t;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 0; i<300; i++)
			for (int j = 0; j<300; j++)
				if (i == j) Map[i][j] = 0;
				else Map[i][j] = Max;
				for (int i = 1; i <= m; i++)
				{
					scanf("%d%d%d", &a, &b, &x);
					if (Map[a + 1][b + 1]>x) Map[a + 1][b + 1] = Map[b + 1][a + 1] = x;
				}
				scanf("%d%d", &s, &t);
				dijkstra(n, m, s + 1, t + 1);
				if (dis[t + 1] != Max) printf("%d\n", dis[t + 1]);
				else printf("-1\n");
	}
	return 0;
}




Dijkstra+heap：

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
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max = 21000000;
typedef pair<int, int> Pair;
int dis[300], head[300];
int S, T, m, n, tail;
priority_queue< Pair, vector<Pair>, greater<Pair> > Q;
struct data
{
	int w, to, next;
}edge[3000], k;
void build(int a, int b, int x)
{
	edge[tail].w = x;
	edge[tail].to = b;
	edge[tail].next = head[a];
	head[a] = tail++;
}
void Dijkstra()
{
	Pair s;
	int v, val;
	dis[S] = 0;
	s.first = 0;
	s.second = S;
	Q.push(s);
	while (!Q.empty())
	{
		Pair u = Q.top();
		Q.pop();
		val = u.first;
		v = u.second;
		if (dis[v]<val) continue;
		for (int i = head[v]; i != -1; i = edge[i].next)
		{
			k = edge[i];
			if (dis[k.to]>dis[v] + k.w)
			{
				dis[k.to] = dis[v] + k.w;
				Q.push(Pair(dis[k.to], k.to));
			}
		}
	}
}
int main()
{
	int a, b, x;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 0; i<300; i++) dis[i] = Max;
		for (int i = 0; i<300; i++) head[i] = -1;
		tail = 0;
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &a, &b, &x);
			build(a, b, x);
			build(b, a, x);
		}
		scanf("%d%d", &S, &T);
		Dijkstra();
		if (dis[T] != Max) printf("%d\n", dis[T]);
		else printf("-1\n");
	}
	return 0;
}
文章目录
  1. 1. 题目描述
  2. 2. 思路
  3. 3. FLoyd
  4. 4. Bellman_Ford：
  5. 5. Dijkstra 没优化+邻接矩阵：
  6. 6. Dijkstra+heap：
|