hdu 3191 How Many Paths Are There 次短路条数和长度模板

缘起

继续学习次短路~ hdu 3191 How Many Paths Are There

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
求出次短路的长度和条数

【输入】
多样例. 每个样例有4个整数  N, M, S, E (3 <= N <= 50, 0 <= S , E <N)
N代表节点的个数, M代表有向弧的条数.S是起点, E是终点。
然后M行, 每行形如 x y w, 表示一条x到y的弧,弧长是w, 所有顶点的标号是0~N-1
输入保证没有圈

【输出】
对每个样例输出次短路的长度和条数.

【样例输入】
3 3 0 2
0 2 5
0 1 4
1 2 2

【样例输出】
6 1

【限制】
1s

上【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
92
93
94
95
96
97
98
99
100
101
102
103
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 55;
int n,m,s,e, cnt,head[maxn],d[maxn][2],num[maxn][2];
bool v[maxn][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;
}g[maxn*maxn];

void addarc(int from,int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].len = len;
	head[from] = cnt++;
}

void dijkstra()
{
	memset(d,0x3f,sizeof(d));
	memset(num,0,sizeof(num));
	memset(v,0,sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK> pq;
	pq.push(KK(s,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;
				num[to][1] = num[to][0];
				num[to][0] = num[h][flag];
				pq.push(KK(to, d[to][0], 0));
				pq.push(KK(to, d[to][1], 1));
			}
			else if (!v[to][0] && d[to][0] == t)
			{
				num[to][0]+=num[h][flag];
			}
			else if (!v[to][1] && d[to][1]>t)
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to,d[to][1], 1));
			}
			else if (!v[to][1] && d[to][1] == t)
			{
				num[to][1]+=num[h][flag];
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d%d", &n,&m,&s,&e))
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		while(m--)
		{
			int x,y,w;
			scanf("%d%d%d", &x,&y,&w);
			addarc(x,y,w);
		}
		dijkstra();
		printf("%d %d\n", d[e][1], num[e][1]);
	}
	return 0;
}

但是wa掉了, wa的原因是因为存在0权弧.

1
2
3
4
5
6
4 5 0 2
0 2 1
0 1 1
1 2 2
1 3 2
3 2 0

答案应该是 3 2 但是上面的代码给出的答案是 3 1 后来在discuss区看到有人说要用朴素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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>

const int maxN=55,maxM=3000,inf=0x3f3f3f3f;
struct arc
{
	int from,to,nxt,w;

	arc(){}

	arc(int from_,int to_,int nxt_,int w_):from(from_),to(to_),nxt(nxt_),w(w_){}
}g[maxM];
int n,m,s,e,head[maxN],eg,cnt[maxN][2],vis[maxN][2],dis[maxN][2];

inline void add_arc(int i,int j,int w){g[eg]=arc(i,j,head[i],w),head[i]=eg++;}

void build()
{
	eg=0,memset(head,-1,sizeof(head));
	while (m--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add_arc(a,b,c);
	}
}

void dijkstra(int src,int des)
{
	for (int i = 0; i < n; i++)	vis[i][0]=vis[i][1]=cnt[i][0]=cnt[i][1]=0,dis[i][0]=dis[i][1]=inf;
	dis[src][0]=0,cnt[src][0]=1;
	for (int i = 0; i < 2*n-1; i++)
	{
		int t=inf,k,flag;
		for (int j = 0; j < n; j++)		
			if (!vis[j][0]&&t>dis[j][0])			
				t=dis[j][0],k=j,flag=0;
		for (int j = 0; j < n; j++)		
			if (!vis[j][1]&&t>dis[j][1])			
				t=dis[j][1],k=j,flag=1;	
		if (t==inf) break;	
		vis[k][flag]=1;
		for (int j = head[k]; ~j  ; j=g[j].nxt)
		{
			int tt=t+g[j].w,v=g[j].to;
			if (tt<dis[v][0])
			{
				dis[v][1]=dis[v][0];
				dis[v][0]=tt;
				cnt[v][1]=cnt[v][0];
				cnt[v][0]=cnt[k][flag];
			}
			else if (tt==dis[v][0])			
				cnt[v][0]+=cnt[k][flag];
			else if (tt<dis[v][1])
			{
				dis[v][1]=tt;
				cnt[v][1]=cnt[k][flag];	
			}
			else if (tt==dis[v][1])			
				cnt[v][1]+=cnt[k][flag];			
		}
	}
	printf("%d %d\n",dis[e][1],cnt[e][1]);
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	while (~scanf("%d%d%d%d",&n,&m,&s,&e))
	{
		build();
		dijkstra(s,e);
	}
	return 0;
}

ac情况

Status Accepted
Memory 1212kB
Length 1534
Lang G++
Submitted 2019-10-28 21:55:13
Shared
RemoteRunId 31157285

为什么需要循环2n-1次（上面代码33行）? 

1
2
3
4
5
为什么我们要循环2*n-1次？
显然这道题中我们每一条边都需要考虑、这不是在求最短的一条，说白了是让你求出所有的可能组合，
那么我们势必对每一种情况都需要遍历一次，虽然中间有重复。最短路里已知[start][0]已被标记为访问过，
那么就只有n-1次遍历了，而次短路我们则需要遍历n次(因为一开始标记的是最短路而不是次短路)，这样两者加起来
就为2*n-1次。

后记

其实关于上面wa掉的优先队列优化的dijkstra求次短路，错误的关键原因在于代码第75行

1
2
3
4
else if (!v[to][1] && d[to][1] == t)
{
	num[to][1]+=num[h][flag];
}

对于上面给出的造成wa测试数据, to=2, t=3, 即(3,0)的到来本来想加上3->2的0弧, 然后进入第3行, 使得num[2][1] 得到正确的2的时候, v[to][1]已经是true了（它出堆过, 根本原因是因为到了3的时候, 就是c=3的节点进堆了, 造成(2,1)出堆），所以上面代码段的第三行就不会执行. 所以得到了错误的num[2][1] = 1. 所以我将上面代码段的else if 中的 !v[to][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
92
93
94
95
96
97
98
99
100
101
102
103
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 55;
int n,m,s,e, cnt,head[maxn],d[maxn][2],num[maxn][2];
bool v[maxn][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;
}g[maxn*maxn];

void addarc(int from,int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].len = len;
	head[from] = cnt++;
}

void dijkstra()
{
	memset(d,0x3f,sizeof(d));
	memset(num,0,sizeof(num));
	memset(v,0,sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK> pq;
	pq.push(KK(s,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 (d[to][0]>t) // 去掉了!v[][]的判断
			{
				d[to][1] = d[to][0];
				d[to][0] = t;
				num[to][1] = num[to][0];
				num[to][0] = num[h][flag];
				pq.push(KK(to, d[to][0], 0));
				pq.push(KK(to, d[to][1], 1));
			}
			else if (d[to][0] == t) // 去掉了!v[][]的判断
			{
				num[to][0]+=num[h][flag];
			}
			else if (d[to][1]>t) // 去掉了!v[][]的判断
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to,d[to][1], 1));
			}
			else if (d[to][1] == t) // 去掉了!v[][]的判断
			{
				num[to][1]+=num[h][flag];
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d%d", &n,&m,&s,&e))
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		while(m--)
		{
			int x,y,w;
			scanf("%d%d%d", &x,&y,&w);
			addarc(x,y,w);
		}
		dijkstra();
		printf("%d %d\n", d[e][1], num[e][1]);
	}
	return 0;
}

但是还是wa掉了~ 不造为啥?

参考

【1】https://yfsyfs.github.io/2019/10/28/poj-3463-Sightseeing-最短路次短路的条数-dijkstra/