一次讲透次短路及条数问题，详细探讨dijkstra算法的本质
第一篇
缘起
继续学习次短路~ hdu 3191 How Many Paths Are There
分析
给定一张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】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/
【1】中说了, 它那里的板子只对正权图有效, 而本题可能有0权，所以如果直接上【1】的板子, 代码没写注释,详细注释参见【1】
//#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权弧. 例如反例数据如下
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
#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行）?
为什么我们要循环2*n-1次？
因为求出单源最短至多n-1次松弛, 而单源次短需要n次松弛, 相加就是 2n-1次.
什么? 难理解? 其实你如果理解了【2】就好办了. 因为最短路、次短路一共2n个状态, 但是源的最短路状态是
已经求出的. 所以剩下2n-1个状态, 他们放进堆中, 出一个状态少一个状态. 不就是2n-1了么?
可是朴素的 dijkstra从来都不是我的重点~
挣扎 抛开【1】中讲解的大道理不谈，咱们先谈wa的细节, 对于上面wa掉的优先队列优化的dijkstra求次短路，用给出的反例数据进行debug的时候发现错误的关键原因在于代码第75行
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加上以防止少算. 即写下如下代码。
//#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掉了~ 因为还有如下反例数据（自己对拍造出来的）.
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行, 即
if (v[h][flag])
{
continue;
}
也给去了? 但是这个想法马上被打脸, 连题目给的样例都过不去. 其实如果对于求最（次）短路长度本身是不会有任何影响了——顶多影响效率，多做无意义的其实根本不可能发生的松弛. 但是对于求条数就是重复算了好多次. 怎么理解? 很好理解嘛~ 因为上面第47行保证了上面代码67行和77行
num[to][0]+=num[h][flag];
num[to][0] 种方案和 num[h][flag] 种方案没有相同的~ 为什么能保证? 因为(h,flag)是第一次出现嘛~ 已经出现的都会被47行挡掉嘛~
后来网上找题解, 碰到一个大佬说KK结构体如果距离c相等的话, 要按照顶点标号排序. 不然会wa. 于是试了一波~ 真A了
//#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;
}
但是注意, 这里将之前的v[][] 判断又加回来了. 前面wa掉的数据得到的依旧是 3 1 这个错误答案, 但是依旧ac了. 可见题目的数据很水~
于是, 我将v[][] 的判断条件去掉了. 也a了. 而且上面wa掉的数据也得出了正确的答案 3 2.
//#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;
}
还有热心网友 rm -rf 提供了更加疯（bao）狂（li）的想法（果然,想法和他的名字一样疯狂）——题目的顶点数目太少——区区50, 直接暴力, 搜索出到达终点的所有路径.
//#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区，发现了狗血的一幕
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】
//#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！！！
第一篇结束~
第二篇
poj 3463 Sightseeing 正权有向图最短路次短路的条数和长度模板
缘起
【1】和【2】中我们通过dijkstra、spfa两种方法给出了次短路模板. 现在我们研究次短路的条数问题. poj 3463 Sightseeing
分析
旅行团每天固定的从S地出发到达F地，为了省油要求尽量走最短路径或恰好比最短路径长1单位距离的路径
求满足条件的路径条数
【输入】
多样例.第一行是样例数. 然后每个样例开始于n和m,
2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000
n是城市的个数, m是有向弧（即单向的）的条数. 然后是m行, 每行三个正整数A,B,L,
1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000,
表示从A到B的弧长L
最后一行是两个整数S和F, 1 ≤ S, F ≤ N and S != F, 即为题目中的起点和终点.
【输出】
对每个样例, 输出最短路或者恰好比它长1的次短路的条数之和. 输入保证答案最多1e9条。
【样例输入】
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1
【样例输出】
3
2
【限制】
2s
引用链接：
【1】https://yfsyfs.github.io/2019/08/21/poj-3255-Roadblocks-dijkstra/
【2】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/
【3】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/
【4】https://yfsyfs.github.io/2019/10/29/hdu-3191-How-Many-Paths-Are-There-%E5%90%AB0%E6%9D%83%E5%BC%A7%E7%9A%84%E9%9D%9E%E8%B4%9F%E6%9D%83%E6%9C%89%E5%90%91%E5%9B%BE%E6%AC%A1%E7%9F%AD%E8%B7%AF%E6%9D%A1%E6%95%B0%E5%92%8C%E9%95%BF%E5%BA%A6%E6%A8%A1%E6%9D%BF/
其实和【1】、【2】一样,也都是在跑dijkstra或者spfa的时候顺便维护一些事情而已. 但是本文结合了【3】的优化（更快的板子）以及使用了比【1】、【2】更好理解的方式（之所以说是更加好的理解方式是因为它每次从堆中弹出的状态区分了到底是最短路还是次短路（通过flag），其实flag的作用根本不在于鉴别最短路还是次短路(代码里面根本没有用flag进行判断的),而是在于44行防止重复计数num.也就是说, 如果不是本题要计数num的话, 根本没必要使用flag）， 即下面的 if…else if…else if… 仅仅针对当前出堆的状态来更新. 以后做次短路就用这种方式, 学到了~
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f; // d[i][0](d[i][1])是到达i顶点的最（次）短路, num[i][0]（num[i][1]）是到达i顶点的最（次）短路的条数
struct KK
{
int v, c, flag; // v表示顶点, c表示路径长度, flag=0表示最短路,flag=1表示次短路
KK(int v,int c,int flag):v(v),c(c),flag(flag){}
bool operator <(const KK &o) const
{
return c>o.c; // c越大, 优先级越低
}
};
bool v[maxn][2];
struct Arc
{
int from,to,nxt,len;
}g[maxm];
void addarc(int from, int to, int len)
{
g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
head[from] = cnt++;
}
int solve()
{
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]) // 如果状态达到过, 则不必再扩展了, 这就是【3】中最后提及的优化"更快的板子"
{
continue;
}
v[h][flag] = true;
for (int i = head[h],to, t; ~i; i = g[i].nxt) // 下面的if...else if...else if 更加容易理解~
{
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];
num[to][1] = num[to][0]; // 更新次短路
d[to][0] = t;
num[to][0] = num[h][flag]; // 更新最短路
pq.push(KK(to, d[to][1], 1));
pq.push(KK(to, d[to][0], 0));
}
else if (!v[to][0] && d[to][0] == t) // 更新最短路方法数
{
num[to][0] += num[h][flag]; // 为什么可以直接相加, 是因为(h,flag) 是首次出现(上面的continue起的作用), 所以一定和原先的num[to][0]中的方案不重复,因为(h,flag)是新拓展(44行保证它从未出现过)出的状态.
}
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]; // 能直接相加的原因和上面更新最短路方法数的理由相同
}
}
}
if (d[f][0]+1==d[f][1]) // 如果次短路的确仅仅比最短路长1的话
{
num[f][0] += num[f][1];
}
return num[f][0];
}
int main()
{
#ifdef LOCAL
freopen("d:\data.in", "r", stdin);
//freopen("d:\my.out", "w", stdout);
#endif
int kase;
scanf("%d", &kase);
while(kase--)
{
cnt = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n,&m);
while(m--)
{
int a,b,l;
scanf("%d%d%d", &a, &b, &l);
addarc(a,b,l);
}
scanf("%d%d", &s, &f);
printf("%d\n", solve());
}
return 0;
}
ac情况
Status Accepted Time 32ms Memory 408kB Length 2357 Lang C++ Submitted 2019-10-28 16:44:55 Shared RemoteRunId 20997897
其实, 在松弛的时候不加 !v[][] 这样的判断也是可以的.
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f;
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;
}
};
bool v[maxn][2];
struct Arc
{
int from,to,nxt,len;
}g[maxm];
void addarc(int from, int to, int len)
{
g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
head[from] = cnt++;
}
int solve()
{
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];
num[to][1] = num[to][0];
d[to][0] = t;
num[to][0] = num[h][flag];
pq.push(KK(to, d[to][1], 1));
pq.push(KK(to, d[to][0], 0));
}
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];
}
}
}
if (d[f][0]+1==d[f][1])
{
num[f][0] += num[f][1];
}
return num[f][0];
}
int main()
{
#ifdef LOCAL
freopen("d:\data.in", "r", stdin);
//freopen("d:\my.out", "w", stdout);
#endif
int kase;
scanf("%d", &kase);
while(kase--)
{
cnt = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n,&m);
while(m--)
{
int a,b,l;
scanf("%d%d%d", &a, &b, &l);
addarc(a,b,l);
}
scanf("%d%d", &s, &f);
printf("%d\n", solve());
}
return 0;
}
ac情况
Status Accepted Time 32ms Memory 412kB Length 2305 Lang C++ Submitted 2019-10-29 07:28:21 Shared RemoteRunId 21000037
综合上面两份代码, 我们考虑2个问题
为什么能保证一旦一个状态 v,flag 出堆之后, 该状态的num和d（即 num[v][flag] 和 d[v][flag] ） 就一定已经算好了.
为什么第二份ac代码中第53行可以去掉!v[to][0/1] 这样的判断也是可以的. 首先回答第一个问题. 其实类似的技巧已经在【3】中用过了. 反证法~
如果存在还没有出现的方案的话, 即存在某个点A, 使得A的某个状态(A,flag1)能（非严格）松弛当前出堆的状态 (v, flag). 则因为题目给定的图的权是严格正的. 所以(A,flag1)作为KK结构体的c属性一定严格<当前出堆的(v,flag)作为KK结构体的c属性. 但是按照我们使用小根堆, (A,flag1) 一定在(v,flag)前面出堆. 所以(A,flag1)已经出堆了（因为(v,flag)是当前出堆元素）, 而如果已经出堆的话, 则代码中的第44行是不会允许(A, flag1)去松弛(v,flag)的. 换言之, 能（非严格）松弛(v,flag)的状态一定已经全部出堆了. 所以一旦(v,flag)出堆了, 则它的num也好, d也好, 一定都算好了.
ps: 这里的非严格的意思就是允许>= 而不是严格的 >
再回答第二个问题. 其实和第一个问题是一个问题. 代码中的第49行的for循环中有4个if. 能进入到这4个if中都表示发生了（非严格）松弛. 而根据第一个问题的分析, 意味着被松弛的状态 (to,0/1) 一定是没有出堆的. 所以
v[to][0/1] 一定是false. 所以加不加!v[to][0/1] 这样的判断无所谓. 其实对于【3】文中的”其次”（【3】中全文检索一下”其次”就找到了）, 道理也是如此（即如果d[to]>g[x].len+d[h]的话, 则to一定没有出堆,否则h肯定先于to出堆, h就不可能是代码中当前出堆的元素了 ）——即【3】中代码的45行的
if (!v[to] && d[to]>g[x].len+d[h])
完全可以改成
if (d[to]>g[x].len+d[h])
从上面的分析就知道, 本题的正权条件对于上面的算法的真确性是本质的. 而【4】就缺失了这一条件. 这会导致【4】中的算法会发生根本性的变化. 感兴趣的读者可以参考【4】中的论述.
第三题
hdu 2544 dijkstra模板
缘起
学了dijkstra这么重要的算法（这可是拿图灵奖的算法），怎么能没有一块趁手的板子呢? 遂找到 hdu 2544 最短路 来学习一下.
分析
题目是中文的.
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运
回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
【输入】
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的
路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3
个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这
条路。 输入保证至少存在1条商店到赛场的路线。
【输出】
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
【样例输入】
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
【样例输出】
3
2
【限制】
Time limit 1000 ms
Memory limit 32768 kB
【来源】
UESTC 6th Programming Contest Online
本题是dijkstra的裸题. 但是考虑到是无向图，而且边的条数众多, 所以使用邻接多重表存储图比较好.
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
typedef pair<int, int> P;
//#define LOCAL
const int maxn = 105, maxm = 20005;
int n,m, head[maxn], cnt,d[maxn]; // cnt是弧的数量
struct Arc
{
int from, to, nxt, len; // 一条从from到to的弧, 长度为len, nxt是从from出发的下一条弧
Arc(){}
Arc(int from, int to,int nxt, int len):from(from),to(to), nxt(nxt),len(len){}
}g[maxm]; // g是弧的数组
void addarc(int a, int b, int c)
{
g[cnt] = Arc(a,b,head[a], c);
head[a]=cnt++; // 头插入g[cnt]这条弧到head[a]去
g[cnt] = Arc(b,a,head[b], c);
head[b] = cnt++;
}
int dijkstra()
{
priority_queue<P, vector<P>, greater<P> > pq; // 小根堆(P的first是距离, 越小, 优先级越大, second是顶点标号)
pq.push(P(0,1));
while(!pq.empty())
{
P top = pq.top();
pq.pop();
int h = top.second; // 得到此次用于松弛各最短距离的顶点
for (int x = head[h]; ~x; x = g[x].nxt) // x是弧的编号, 这里是在遍历所有从x出发的弧
{
int to = g[x].to; // g[x].from = h
if (d[to]>g[x].len+d[h]) // 用g[x]这条从h出发,终于to的弧尝试松弛d[to]
{
d[to] = g[x].len+d[h];
pq.push(P(d[to],to));
}
}
}
return d[n];
}
int main()
{
#ifdef LOCAL
freopen("d:\data.in", "r", stdin);
//freopen("d:\my.out", "w", stdout);
#endif
while(scanf("%d%d", &n,&m), n||m)
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(d, 0x3f, sizeof(d));
d[1] = 0;
while (m--)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
addarc(a,b,c);
}
printf("%d\n", dijkstra());
}
return 0;
}
ac情况（C++提交编译会报错, 需要以G++提交）
Status Accepted Time 15ms Memory 1348kB Length 1374 Lang G++ Submitted 2019-08-22 10:23:00 Shared RemoteRunId 30384976
这里需要解释一下上面的dijkstra算法. 这是网上流传比较多的板子. 和之前我用的那种有 inU数组的不一样. 因为流程是每次pop出最短的，然后使用这个最短的距离尝试松弛各个顶点到单源的距离. 注意，dijkstra算法其实也是基于dp的思想，因为你想啊，每个顶点u到单源1的最短距离肯定有一个前置顶点v（v可能就是单源1）吧? 即u的前一步是v. 那么可以断言1到v的距离一定是最短的. 不然的话, 可以松弛1到v的距离来达到到达u的更短距离. 只是未必是DAG，所以你不知道从哪个顶点开始求起. 所以DAG图的单源最短路径算法是更简单的.
回到正题，为什么不需要每次将上一轮已经在pq中的元素全部pop出来再将本轮松弛的结果push进去? 因为前一轮push进去的根本没机会pop出来. 因为本轮就是在上一轮的基础上push进去的. 所以上一轮push进去的结果不可能成为本轮最小的pop出来. 所以可以这么搞.
更快的板子 其实看看上面的板子, 如果和之前O(n^2)朴素的dijkstra算法比较, 就感觉上面的板子有点冗余——比如一个点已经曾经作为堆的top出来过. 现在又出来了, 则它还需要去松弛其他弧吗? 显然是不需要的. 可以直接continue掉.
典型例子可以参见下图
(5,4)即4距离单源路径为5肯定进入过堆（事实上, 第一轮扫描就进入了堆），所以一定有出堆的时候（因为最后要堆空的），但是（4,4） 也进入过堆（由3去松弛3->4 这条从3出发的弧），而且（4,4）在(5,4)之前出堆（因为4<5）, 那么等到(5,4)出堆的时候显然不需要再用5去松弛其他从4出发的弧，也就是(5,4)出堆之后, 直接continue掉就好了. 究其根本是因为4既然已经作为堆顶元素出过堆, 所以它已经达到单源最短了. 后面出堆的(5,4)的5一定不是到4的最短路. 那你用5去松弛从4出发的弧有何意义呢? 因为我已经用4去松弛过从4出发的弧了（(4,4)出堆的时候）. 其次, 在松弛其他弧的时候, 对于已经达到最短路的点不需要去松弛（即已经出过堆的点），例如上图中出堆的(3,2)不需要去松弛已经出堆的3，因为3已经达到最短路2了（如果存在还能真正意义上松弛（即真的能减小距离）已经出堆的点的话, 例如当前出堆的(A,B) 还能真正松弛已经出堆的(C,D),即A+|B-D|<C, 这里严格< 就体现”真正”二字. 则因为非负权（所以对于dijkstra而言,非负权这个条件是本质的）, 则A<C, 那么根据算法使用小根堆, 怎么会(A,B)在(C,D)后面才出堆呢? 矛盾! 所以不可能在一个点出堆之后还发生真正意义上松弛,但是A+|B-D|==C 即非严格的松弛是可能的发生的，但是非严格意义上的松弛的发生并不会影响最短路长度的最后计算值. 所以完全可以不理会。综上2点，我们可以得到更快的dijkstra的板子（或者说和朴素O(n^2)dijkstra实现更贴近的板子）
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
typedef pair<int, int> P;
//#define LOCAL
const int maxn = 105, maxm = 20005;
int n,m, head[maxn], cnt,d[maxn];
bool v[maxn];
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[maxm];
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(v,0,sizeof(v));
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;
if (v[h])
{
continue; // 对于已经出过堆（即达到最短路径的）点, top->first肯定>=h的单源最短,所以不需要再用h去松弛从h出发的其他弧了
}
v[h] = true;
for (int x = head[h]; ~x; x = g[x].nxt)
{
int to = g[x].to;
if (!v[to] && d[to]>g[x].len+d[h]) // 对于已经到达最短路径的to,也不需要去松弛了
{
d[to] = g[x].len+d[h];
pq.push(P(d[to],to));
}
}
}
return d[n];
}
int main()
{
#ifdef LOCAL
freopen("d:\data.in", "r", stdin);
//freopen("d:\my.out", "w", stdout);
#endif
while(scanf("%d%d", &n,&m), n||m)
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(d, 0x3f, sizeof(d));
d[1] = 0;
while (m--)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
addarc(a,b,c);
}
printf("%d\n", dijkstra());
}
return 0;
}
ac情况（0ms） Status Accepted Memory 1352kB Length 1382 Lang G++ Submitted 2019-10-28 16:18:52 Shared RemoteRunId 31149262
所以如果有人现在再问我——dijkstra为什么能保证算法正确? 我会告诉TA
因为dijkstra算法保证了已经出堆的元素后续不可能发生严格意义上的松弛（但是非严格意义上的松弛还是可能发生的）, 证明见上面的反证法. 其中体现了dijkstra算法对于非负权条件本质的依赖. 所以对于负权图, dijkstra算法是不正确的.
特别地, 如果是正权（有向）图, 则所有的松弛都是严格意义上的松弛, 所以对于正权（有向）图，dijkstra算法保证了已经出堆的元素后续甚至不可能发生非严格意义上的松弛.
因为一旦已经出堆就不可能被严格意义上松弛, 所以dijkstra算法一定在有限步结束, 而且对于含圈的非负权（有向）图也是适用的（因为上面的分析并没有用到”此图必须无圈”这种条件）.
腾讯云开发者
