poj 3255 Roadblocks dijkstra

缘起

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
贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，
于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 
贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个(可见是稀疏图,不能用邻接矩阵)。
贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，
可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须>最短路（可能有多条）的长度，
但它的长度必须<=所有除最短路外的路径的长度。

Input
* 第1行: 两个整数，N和R，用空格隔开 * 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B
Output
* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度
Sample Input
4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

输出说明:

最短路：1-> 2 -> 4 (长度为100+200=300)
第二短路：1 -> 2 -> 3 -> 4

(长度为100+250+100=450)
本题只需要处理一组数据

限制
Time Limit: 2000MS		Memory Limit: 65536K

来源
USACO 2006 November Gold

其实就是利用了一点

次短路只可能有最短路+松弛边或者次短路+松弛边构成, 所以只需要在经典的dijkstra算法过程中也要压入次短路结果来维护次短路数组dd即可. 下面的代码是我自己写的.

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
80
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
//#define LOCAL
typedef pair<int,int> P;

int n,r, head[5005], cnt, d[5005], dd[5005]; // d是最短距离数组, dd是次短距离数组

struct Arc
{
	int from, to, nxt, len;
	Arc(){}
	Arc(int from, int to, int nxt, int len):from(from), to(to), nxt(nxt), len(len){}
}g[200005];

void addArc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]= cnt++;
	g[cnt] = Arc(b,a,head[b], c);
	head[b]= cnt++;
}

int dijkstra()
{
	priority_queue<P,vector<P>, greater<P> > pq;
	pq.push(P(0,1));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		int h = top.second;
		for (int i = head[h]; ~i; i = g[i].nxt)
		{
			int to = g[i].to, t = d[h]+g[i].len, tt = dd[h]+g[i].len; // 次短边只可能是由最短边或者次短边进行松弛, 其实就是 tmp这四个元素排决出第一和第二. 
			int tmp[4];
			tmp[0] = d[to], tmp[1] = dd[to], tmp[2] = t, tmp[3] = tt; // 短平快~ 直接sort
			sort(tmp, tmp+4);
			if (d[to]>tmp[0])
			{
				d[to] = tmp[0];
				pq.push(P(d[to], to));
			}
			int x = 1;
			while(x<4&&tmp[x]==tmp[0]) x++; // 因为本题的次短路是严格次短路（即要真的比最短路严格大）, 所以要这样——只有真的比最短路短才更新
			if (x <4 && dd[to]> tmp[x])
			{
				dd[to] = tmp[x];
				pq.push(P(dd[to], to));
			}
		}
	}
	return dd[n];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&r);
	memset(head,-1, sizeof(head));
	memset(d, 0x3f, sizeof(d));
	memset(dd, 0x3f, sizeof(dd));
	d[1] = 0;
	while(r--)
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	}
	printf("%d\n", dijkstra());
	return 0;
}

ac情况

20788439 yfsyfs 3255 Accepted 4112K 235MS G++ 1599B 2019-08-22 19:24:29

其实这种理解方式并不好, 更好的方式是 【1】， 使用【1】的方式可以给出如下更快的代码(代码详细注释参见【1】)

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
80
81
82
83
84
85
86
87
88
89
90
91
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
//#define LOCAL

int n,r, head[5005], cnt, d[5005][2]; // d[i][0]是到i的最短路, d[i][1]是到i的次短路
bool v[5005][2];

struct KK
{
	int v,c,flag;
	KK(int v,int c,int flag):v(v),c(c),flag(flag){}
	bool operator<(const KK &o) const
	{
		return c>o.c;
	}
};

struct Arc
{
	int from, to, nxt, len;
	Arc(){}
	Arc(int from, int to, int nxt, int len):from(from), to(to), nxt(nxt), len(len){}
}g[200005];

void addArc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]= cnt++;
	g[cnt] = Arc(b,a,head[b], c);
	head[b]= cnt++;
}

int dijkstra()
{
	memset(d, 0x3f, sizeof(d));
	memset(v,0,sizeof(v));
	d[1][0] = 0;
	priority_queue<KK> pq;
	pq.push(KK(1,0,0));
	while(!pq.empty())
	{
		KK top = pq.top();
		pq.pop();
		int h = top.v, flag = top.flag;
		if (v[h][flag])
		{
			continue;
		}
		v[h][flag] = true;
		for (int i = head[h],to,t; ~i; i = g[i].nxt)
		{
			to = g[i].to, t = d[h][flag]+g[i].len;
			if (!v[to][0] && d[to][0]>t)
			{
				d[to][1] = d[to][0];
				d[to][0] = t;
				pq.push(KK(to,d[to][0], 0));
				pq.push(KK(to,d[to][1], 1));
			}
			else if (!v[to][1] && d[to][1]>t)
			{
				d[to][1] = t;
				pq.push(KK(to, d[to][1], 1));
			}
		}
	}
	return d[n][1];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&r);
	memset(head,-1, sizeof(head));
	while(r--)
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	}
	printf("%d\n", dijkstra());
	return 0;
}

ac情况

Status Accepted
Time 172ms
Memory 4128kB
Length 1591
Lang C++
Submitted 2019-10-28 17:03:12
Shared
RemoteRunId 20997964

参考

【1】https://yfsyfs.github.io/2019/10/28/poj-3463-Sightseeing-%E6%9C%80%E7%9F%AD%E8%B7%AF%E6%AC%A1%E7%9F%AD%E8%B7%AF%E7%9A%84%E6%9D%A1%E6%95%B0-dijkstra/