hdu 3191 How Many Paths Are There 含0权弧的非负权有向图次短路条数和长度模板

缘起

继续学习次短路~ 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
给定一张DAG（非负权，但是可能有0权）, 求出次短路的长度和条数

【输入】
多样例. 每个样例有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】中说了, 它那里的板子只对正权图有效, 而本题可能有0权，所以如果直接上【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的原因在【1】中已经说过了——是因为存在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 （注意,上面的反例数据可以卡掉不少网上用优先队列优化的dijkstra ac代码, 即本题的数据还是不强的, 关于这个问题后面我还会细说~）

后来在discuss区看到有人说要用朴素dijkstra. 果然能A

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

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

1
2
3
4
为什么我们要循环2*n-1次？
因为求出单源最短至多n-1次松弛, 而单源次短需要n次松弛, 相加就是 2n-1次.
什么? 难理解? 其实你如果理解了【2】就好办了. 因为最短路、次短路一共2n个状态, 但是源的最短路状态是
已经求出的. 所以剩下2n-1个状态, 他们放进堆中, 出一个状态少一个状态. 不就是2n-1了么?

可是朴素O(n^2) 的 dijkstra从来都不是我的重点~

挣扎

抛开【1】中讲解的大道理不谈，咱们先谈wa的细节, 对于上面wa掉的优先队列优化的dijkstra求次短路，用给出的反例数据进行debug的时候发现错误的关键原因在于代码第75行

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

对于上面给出的造成wa测试数据, 我debug的时候发现 to=2 的时候, h = 3, flag = 0（(3,0)就是顶点3的最短路状态）. num[h][flag]=1, num[to][1] = 1, 本来眼看num[to][1]就要加成2了. 但是v[to][1]是true了~ 导致上面的if没进去~ 即(2,1)状态（顶点2的次短路状态，那是次短路长度是c=3）已经出堆啦~ 其实你想想为什么会已经出堆? 因为3->2的弧长是0, 0->1->3 的长度就是1+2=3, 和0->1->2一样长度。而堆中就是按照c的大小形成小根堆的. 所以保不齐 (2,1)状态就会先出堆! 这就是【2】中说的

dijkstra算法保证了已经出堆的状态不会再被严格意义上松弛, 但是非严格意义上被松弛还是有可能的.

这里已经出堆的(2,1)就被尚未出堆的(3,0)状态进行了非严格意义上的松弛. 对于求次短路本身，非严格意义松弛并不重要——不会影响次短路长度本身. 但是如果要求条数的话, 就很重要了——毕竟上面的分析已经表明了非严格松弛的少算会导致次短路条数计数变少诶~ 所以我们耍个小聪明, 把上面的!v[to][1] 验证给去掉. 这样的话，非严格松弛如果在一个已经出堆的状态身上发生的话, 则我依旧将其num加上以防止少算. 即写下如下代码。

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
2
3
4
5
6
7
5 6 1 4
1 4 10
1 4 0
1 2 0
1 3 0
2 3 0
3 4 1

正确的答案是1 2 , 但是上面的代码依旧只给出 1 1 的错误答案.

依旧不谈大道理, 我们就谈wa的细节. 我debug的时候发现wa的根本原因在于2->3的弧长为0，而状态（3,0）先于状态（2,0）出堆了. 而（2,0）的出堆会松弛(3,0)的c值以及num值, (3,0)的出堆会松弛(4,1)的c值以及num值, 关于c值、num值的含义参见【1】中的代码注释. 而正确的顺序应该是这样的

  • (2,0)先出堆，去非严格松弛(3,0)，使得(3,0)的num值, 即num[3][0]变成2，然后(3,0)再去严格松弛(4,1),使得(4,1)的num值, 即 num[4][1]变成2, 这就是正确答案.

但是因为(3,0)先于(2,0) 出堆（注意！为什么能先于(2,0)出堆? 因为2->3的弧长是0, 所以非严格松弛是完全可能发生在一个状态已经出堆之后的，这就是【2】中最后的结论，如果是正权图就不会发生这种情况, 这就是为什么【1】中的板子对本题不适用的原因）, 所以剧本在算法跑的时候变成下面的样子

  • (3,0)先出堆，去严格松弛(4,1)，使得(4,1)的num值, 即num[4][1]变成1，然后(2,0)再去非严格松弛(3,0),使得(3,0)的num值, 即 num[3][0]变成2, 可是, num[3][0]现在变成2又有什么用呢? 它已经出堆了! 不可能再去松弛(4,1)了呀~

于是有一个疯狂的想法——那把上面代码的47行, 即

1
2
3
4
if (v[h][flag])
{
	continue;
}

也给去了? 但是这个想法马上被打脸, 连题目给的样例都过不去. 其实如果对于求最（次）短路长度本身是不会有任何影响了——顶多影响效率，多做无意义的其实根本不可能发生的松弛. 但是对于求条数就是重复算了好多次. 怎么理解? 很好理解嘛~ 因为上面第47行保证了上面代码67行和77行

1
num[to][0]+=num[h][flag];

num[to][0] 种方案和 num[h][flag] 种方案没有相同的~ 为什么能保证? 因为(h,flag)是第一次出现嘛~ 已经出现的都会被47行挡掉嘛~

后来网上找题解, 碰到一个大佬说KK结构体如果距离c相等的话, 要按照顶点标号排序. 不然会wa. 于是试了一波~ 真A了

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
104
105
106
107
//#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
	{
		if (c==o.c)
		{
			return v>o.v;
		}
		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) // 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 (!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;
}

ac情况

Status Accepted
Time 15ms
Memory 1252kB
Length 1861
Lang G++
Submitted 2019-10-29 12:48:58
Shared
RemoteRunId 31163655

但是注意, 这里将之前的v[][] 判断又加回来了. 前面wa掉的数据得到的依旧是 3 1 这个错误答案, 但是依旧ac了. 可见题目的数据很水~

于是, 我将v[][] 的判断条件去掉了. 也a了. 而且上面wa掉的数据也得出了正确的答案 3 2. 

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
104
105
106
107
//#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
	{
		if (c==o.c)
		{
			return v>o.v;
		}
		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)
			{
				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)
			{
				num[to][0]+=num[h][flag];
			}
			else if (d[to][1]>t)
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to,d[to][1], 1));
			}
			else if (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;
}

ac情况（直接G++提交, 干到了0ms~）

Status Accepted
Memory 1256kB
Length 1809
Lang G++
Submitted 2019-10-29 12:58:20
Shared
RemoteRunId 31163788

还有热心网友 rm -rf 提供了更加疯（bao）狂（li）的想法（果然,想法和他的名字一样疯狂）——题目的顶点数目太少——区区50, 直接暴力, 搜索出到达终点的所有路径.

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 "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 55;
int n,m,s,e, cnt,head[maxn],ans[10000000], top; // 这里ans必须开大~
bool v[maxn];

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 dfs(int cur, int len)
{
	if (cur==e)
	{
		ans[top++] = len;
		return;
	}
	for (int h = head[cur],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!v[to])
		{
			v[to] = true;
			dfs(to, len+g[h].len);
			v[to] = false;
		}
	}
}

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 = top = 0;
		memset(head, -1, sizeof(head));
		while(m--)
		{
			int x,y,w;
			scanf("%d%d%d", &x,&y,&w);
			addarc(x,y,w);
		}
		memset(v, 0, sizeof(v));
		v[s] = true;
		dfs(s,0);
		sort(ans, ans+top); // 不管了, 直接暴力sort
		int pos = 1;
		while(pos<top && ans[pos]==ans[0])
		{
			pos++;
		}// ans[pos]>ans[0], 是次短路 
		int dd = 1, pos1 = pos+1;
		while(pos1<top && ans[pos1]==ans[pos])
		{
			++dd;
			++pos1;
		}
		printf("%d %d\n", ans[pos], dd);
	}
	return 0;
}

ac情况

Status Accepted
Time 858ms
Memory 8332kB
Length 1235
Lang C++
Submitted 2019-10-29 17:31:47
Shared
RemoteRunId 31167892

可见, 对于本题，乱搞的做法也是可以接受的（逃）~

反思

本题结束了吗?

其实不然, 因为首先就无法解释为什么朴素O(n^2)能AC, 而优先队列式的dijkstra会wa掉. 其次, 为什么后面让KK的顶点也加入到堆的比较序就可以A了?

其实，在上面分析第二份wa掉的数据的时候我们已经看出端倪了——dijkstra对于含0权的非负权图上求最短路问题时无法阻止已经出堆的状态仍然被后续出堆的状态进行非严格意义下的松弛. 拿上面的例子来说，就是已经出堆的(3,0)仍然会被后续出堆的（2，0）松弛. 但是我们希望的是（2,0） 先出堆，（3,0）再出堆. 而不是反过来，反过来会导致答案的错误——更新(3,0)为2更新晚了 ，(3,0)已经出堆了，无法再更新(4,1)为正确的答案2了.

即我们希望不再发生”已经出堆的状态被当前出堆的状态非严格松弛”这种事情! 这样的话, 就和【1】中正权图是一模一样了！自然就可以得到正确的答案.

但是这偏偏是dijkstra算法无法做到的（事实上，dijkstra算法是做不了本题的）!

所以我们猜测, 不论是朴素O（n^2）dijkstra还是加了KK排序的优先队列式的dijkstra， 都是保证了顶点按照某一次序搜索，从而防止了 “已经出堆的状态被当前出堆的状态非严格松弛” 这种事情的发生的!

后来跑到此题的discuss区，发现了狗血的一幕

1
2
3
4
5
6
7
8
9
10
11
12
Posted by Soal at 2013-04-27 20:26:05 on Problem 3191						(15)	

"我用测试了下这题的数据。
1.有长度为0的边
2.出题人偷懒，为了保证无环，造出的边u,v,d，总是有u<v

对于1的情况， 如果有这样的一条边 u,v,0 则u必须先更新，在这题的数据总是有u<v。每次朴素拿出来更新的点总
是编号最小的，所以能AC，而用优先队列优化的，在重载的<中，只是比较距离大小是不够的，不能保证u在v之前更
新。所以出现discuss里说的，用优先队列WA，用朴素AC的情况。而网上的一些用优先队列AC的题解中，在重载的<
中比较了编号大小，侥幸AC，但不正确。

我的做法是，应该是拓扑排序之后，根据拓扑序做DP，这样对于u,v,0这样的边，u总是先更新，保证了正确性。"

看来所见略同啊~ 因为朴素dijkstra和加了排序的KK保证了顶点小的先被搜到（先出堆）！而本题的数据又恰好满足了所有弧（特别的，0权弧）u->v 则 u<v, . 所以我们dijkstra的时候就能保证顶点标号小的（即弧的起点）先出堆，就不会发生”已经出堆的状态被当前出堆的状态非严格松弛”这种事情了！但是第一份wa掉的测试数据就已经说明这纯粹是侥幸AC了.

重生

那么正确的思路应该是什么?

首先，防止”已经出堆的状态被当前出堆的状态非严格松弛” 意味着什么呢?

意味着, 如果有0权弧A->B 则A的状态要先出堆, 然后用A的状态根据弧A->B 去松弛B的状态!

等等! 这不是DAG么? 本题是DAG啊! 所以正确的思路应该是在拓扑序下DP。 拓扑排序不清楚的童鞋可以参考【3】，而且下面的代码的tmp+sort的代码参见了【4】、【5】

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 55;
int n,m,s,e, cnt,cntt,head[maxn],headd[maxn],d[maxn][2], num[maxn][2],indeg[maxn]; // d[i][0/1]是s到顶点i的最短/次短路长度, num[i][1/0]是s到顶点i的最短/次短路条数
bool v[maxn];

struct Arc
{
	int from,to,nxt,len;
}g[maxn*maxn],gg[maxn*maxn]; // (cntt,headd,gg) 是 (cnt, head, g)的反向建图

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 addarcc(int from,int to, int len)
{
	gg[cntt].from = from, gg[cntt].to = to, gg[cntt].nxt = headd[from], gg[cntt].len = len;
	headd[from] = cntt++;
}

struct KK
{
	int d,num;
	bool operator<(KK &o)
	{
		return d<o.d;
	}
}tmp[4];

void topsort()
{
	memset(d, 1, sizeof(d));
	memset(num, 0, sizeof(num));
	d[s][0]=0, num[s][0] = 1;
	stack<int> s;
	for (int i = 0;i<n; i++)
	{
		if (!indeg[i])
		{
			s.push(i);
		}
	}
	while(!s.empty())
	{
		int top = s.top();
		s.pop();
		for (int h = head[top],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!--indeg[to])
			{
				s.push(to);
			}
		} // 拓扑排序部分
		for (int h = headd[top],to,t,tt; ~h; h = gg[h].nxt)
		{
			to = gg[h].to;
			t = d[to][0]+gg[h].len;
			tt = d[to][1]+gg[h].len;
			tmp[0].d = d[top][0], tmp[0].num = num[top][0];
			tmp[1].d = d[top][1], tmp[1].num = num[top][1];
			tmp[2].d = t, tmp[2].num = num[to][0];
			tmp[3].d = tt, tmp[3].num = num[to][1];
			sort(tmp, tmp+4);
			if (d[top][0] > tmp[0].d) // 则最短路是tmp[0], 次短路是tmp[1]或者tmp[1]+tmp[2]
			{
				d[top][0] = tmp[0].d;
				num[top][0] = tmp[0].num;
				d[top][1] = tmp[1].d;
				num[top][1] = tmp[1].num;
				if (tmp[1].d==tmp[2].d)
				{
					num[top][1] += tmp[2].num;
				}
			}
			else if (d[top][0] == tmp[0].d) // 则"最短路是 tmp[0]+tmp[1],次短路是tmp[2]或者tmp[2]+tmp[3]"或者"最短路是tmp[0],次短路是tmp[1]或者tmp[1]+tmp[2]"
			{
				if (tmp[0].d==tmp[1].d)
				{
					num[top][0]+=tmp[1].num;
					d[top][1] = tmp[2].d;
					num[top][1] = tmp[2].num;
					if (tmp[2].d==tmp[3].d)
					{
						num[top][1]+=tmp[3].num;
					}
				}
				else
				{
					d[top][1] = tmp[1].d;
					num[top][1] = tmp[1].num;
					if (tmp[1].d==tmp[2].d)
					{
						num[top][1]+=tmp[2].num;
					}
				}
			}
		} // dp部分
	}
}

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 = cntt =  0;
		memset(head, -1, sizeof(head));
		memset(headd, -1, sizeof(headd));
		memset(indeg, 0, sizeof(indeg));
		while(m--)
		{
			int x,y,w;
			scanf("%d%d%d", &x,&y,&w);
			addarc(x,y,w);
			++indeg[y];
			addarcc(y,x,w); // 反向建图
		}
		topsort();
		printf("%d %d\n", d[e][1], num[e][1]);
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 1772kB
Length 2747
Lang C++
Submitted 2019-10-30 07:19:52
RemoteRunId 31179668

这才是真正的AC！！！

参考

【1】https://yfsyfs.github.io/2019/10/29/poj-3463-Sightseeing-%E6%AD%A3%E6%9D%83%E6%9C%89%E5%90%91%E5%9B%BE%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%E5%92%8C%E9%95%BF%E5%BA%A6%E6%A8%A1%E6%9D%BF/

【2】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/

【3】https://yfsyfs.github.io/2019/09/07/hdu-3342-Legal-or-Not-%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F%E6%9D%BF%E9%A2%98/

【4】https://yfsyfs.github.io/2019/10/28/POJ-3255-Roadblocks-%E6%AC%A1%E7%9F%AD%E8%B7%AF%E6%A8%A1%E6%9D%BF-spfa/

【5】https://yfsyfs.github.io/2019/08/21/poj-3255-Roadblocks-dijkstra/