# k 短路问题

### Solution1: 迭代加深搜索

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1001
#define ME 100001
#define MXDIS 100

using namespace std;

int fst[MX],nxt[ME],v[ME],w[ME],lnum;
int fin[MX],nin[ME],vin[ME],win[ME],inum;
int n,m,S,T,K;

void addeg(int nu,int nv,int nw){nxt[++lnum]=fst[nu];fst[nu]=lnum;v[lnum]=nv;w[lnum]=nw;}

void addin(int nu,int nv,int nw){nin[++inum]=fin[nu];fin[nu]=inum;vin[lnum]=nv;win[lnum]=nw;}

void input()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
}
scanf("%d%d%d",&S,&T,&K);
}

int dis[MX],q[MX],inq[MX];
void SPFA(int frm)
{
int t=1,h=0,nu,nv;
for(int i=1;i<=n;i++)dis[i]=99999999;
q[++h]=frm;
dis[frm]=0;
inq[frm]=1;
while(h>=t)
{
nu=q[(t++)%MX];
for(int i=fin[nu];i!=-1;i=nin[i])
{
nv=vin[i];
if(dis[nv]>dis[nu]+win[i])
{
dis[nv]=dis[nu]+win[i];
if(!inq[nv])
{
inq[nv]=1;
q[(++h)%MX]=nv;
}
}
}
inq[nu]=0;
}
}

int ans,top;

void dfs(int x,int now)
{
if(x==T&&now!=0)ans++;
if(ans>=K){cout<<top<<endl;exit(0);}
for(int i=fst[x];i!=-1;i=nxt[i])
{
if(dis[v[i]]+now+w[i]>top)continue;
dfs(v[i],now+w[i]);
}
}

void work()
{
SPFA(T);
if(dis[S]>100000){cout<<-1<<endl;return;}
for(int i=dis[S];i<=dis[S]+MXDIS;i++)
{
ans=0;
top=i;
dfs(S,0);
}
cout<<-1<<endl;
}

void init()
{
memset(fst,0xff,sizeof(fst));
memset(fin,0xff,sizeof(fin));
inum=-1;
lnum=-1;
}

int main()
{
init();
input();
work();
return 0;
}


### Solution2:A*

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define MX 10001
#define ME 100001

using namespace std;

int n,m,k;
int S,T;

struct Node
{
int p,f,h;
bool operator <(const Node a)const
{
if(a.f+a.h<f+h)return 1;
else return 0;
}
Node(int a,int b,int c)
{
this->p=a,this->f=b,this->h=c;
}
};
Node make(int a,int b,int c)
{
Node thi(a,b,c);
return thi;
}

int dis[MX];

class graph
{
public:
int fst[MX],nxt[ME],v[ME],w[ME],lnum;
int q[MX],inq[MX];
priority_queue<Node> mp;
void init()
{
memset(fst,0xff,sizeof(fst));
lnum=-1;
}
void addeg(int nu,int nv,int nw)
{
nxt[++lnum]=fst[nu];
fst[nu]=lnum;
v[lnum]=nv;
w[lnum]=nw;
}
void SPFA(int frm)
{
int h=0,t=1,x,y;
memset(dis,0x3f,sizeof(dis));
q[++h]=frm;
dis[frm]=0;
inq[frm]=1;
while(h>=t)
{
x=q[(t++)%ME];
for(int i=fst[x];i!=-1;i=nxt[i])
{
y=v[i];
if(dis[y]>dis[x]+w[i])
{
dis[y]=dis[x]+w[i];
if(!inq[y])
{
q[(++h)%ME]=y;
inq[y]=1;
}
}
}
inq[x]=0;
}
}
int Astar(int frm,int to)
{
Node x(0,0,0);
int cnt=0;
if(frm==to)k++;
if(dis[frm]>100000)return -1;
mp.push(make(frm,0,dis[frm]));
while(!mp.empty())
{
x=mp.top(),mp.pop();
if(x.p==to)
{
cnt++;
if(cnt==k)return x.f+x.h;
}
for(int i=fst[x.p];i!=-1;i=nxt[i])mp.push(make(v[i],x.f+w[i],dis[v[i]]));
}
return -1;
}

}g1,g2;

void input()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
}
scanf("%d%d%d",&S,&T,&k);
}

int main()
{
g1.init(),g2.init();
input();
g2.SPFA(T);
printf("%d\n",g1.Astar(S,T));
return 0;
}


### Solution3: 可并堆

• $dis(x)$：$x$点沿着最短路树走到 $T$的路径长度。
• $e.s,e.t,e.w$：非树边 $e$的起始节点，终止节点和长度。
• $\Delta e$：从 $e.s$出发走非树边 $e$，再走最短路，比直接走 $e.s$的最短路多走的距离。即 $\Delta e=dis(e.t)+e.w-dis(e.s)$

• 将 $e_m$替换为一条 $\Delta$更大的可行非树边，即 $e_1,e_2\cdots ,e_m’$
• 将序列后面添加上一条 $\Delta$最小的可行非树边，即 $e_1,e_2\cdots ,e_m,e_{m+1}$

• 1. 当所有的路径找完了，需要及时退出，以免 $pop​$一个空的优先队列。
• 2. 当图中根本就没有第二条路径，$S​$的可并堆将是空的，这时候需要直接退出。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#define MX 200008
#define oo 123123123123123

using namespace std;

template <typename T> void read(T& x)
{
x = 0; char c = getchar(); bool f = 0;
while(!isdigit(c) && c!='-') c = getchar();
if(c == '-') f = 1, c = getchar();
while(isdigit(c)) x = x*10+c-'0', c = getchar();
if(f) x = -x;
}

int N, M;
double E;

struct PNODE
{
int p;
double d;

PNODE (const int& p0 = 0, const double& d0 = 0) : p(p0), d(d0) {}
bool operator < (const PNODE& t) const {return d > t.d;}
};

struct SNODE
{
int ls, rs, ed, len;
double w;

SNODE (const int& e0 = 0, const double& w0 = 0) : ls(0), rs(0), ed(e0), len(0), w(w0) {}
};

struct HEAP
{
int cnt;
SNODE tre[MX*6];

int merge(int x, int y)
{
int a;
if(!x || !y) return (x|y);
if(tre[x].w < tre[y].w) swap(x, y);
tre[a = ++cnt] = tre[y];
tre[a].ls = merge(x, tre[y].ls);
if(tre[tre[a].ls].len > tre[tre[a].rs].len) swap(tre[a].ls, tre[a].rs);
tre[a].len = tre[tre[a].ls].len + 1;
return a;
}
};

struct GRAPH
{
int fst[MX], nxt[MX], v[MX], lnum;
int que[MX], inq[MX], pre[MX];
double w[MX], dis[MX];

void addeg(int nu, int nv, double nw)
{
nxt[++lnum] = fst[nu];
fst[nu] = lnum;
v[lnum] = nv;
w[lnum] = nw;
}

void spfa(int frm)
{
int h = 1, t = 1, x, y;
for(int i=1; i<=N; i++) dis[i] = +oo;
que[h] = frm;
dis[frm] = 0;
inq[frm] = 1;
while(h >= t)
{
x = que[(t++)%MX];
inq[x] = 0;
for(int i=fst[x]; i; i=nxt[i])
{
y = v[i];
if(dis[y] > dis[x] + w[i])
{
dis[y] = dis[x] + w[i];
pre[y] = i;
if(!inq[y])
{
que[(++h)%MX] = y;
inq[y] = 1;
}
}
}
}
}
};

HEAP H;
GRAPH G, R;
priority_queue<PNODE> Q;

void input()
{
int a, b; double c;
for(int i=1; i<=M; i++)
{
}
}

PNODE seq[MX];
int rot[MX];

void work()
{
R.spfa(N);
for(int i=1; i<=N; i++) seq[i] = PNODE(i, R.dis[i]);
sort(seq+1, seq+N+1);
for(int a=N; a>=1; a--)
{
int x = seq[a].p;
for(int i=G.fst[x]; i; i=G.nxt[i])
{
if(i != R.pre[x])
{
H.cnt++;
H.tre[H.cnt] = SNODE(G.v[i], R.dis[G.v[i]]-R.dis[R.v[i]]+G.w[i]);
rot[x] = H.merge(rot[x], H.cnt);
}
}
rot[x] = H.merge(rot[x], rot[G.v[R.pre[x]]]);
}
if(rot[1]) Q.push(PNODE(rot[1], H.tre[rot[1]].w));
int cnt = 0;
if(E-R.dis[1] >= 0) E -= R.dis[1], cnt++;
while(E > 0)
{
if(Q.empty()) break;
PNODE e = Q.top();
Q.pop();
if(E-(e.d+R.dis[1]) < 0) break;
else E -= (e.d+R.dis[1]), cnt++;
if(H.tre[e.p].ls) Q.push(PNODE(H.tre[e.p].ls, e.d - H.tre[e.p].w + H.tre[H.tre[e.p].ls].w));
if(H.tre[e.p].rs) Q.push(PNODE(H.tre[e.p].rs, e.d - H.tre[e.p].w + H.tre[H.tre[e.p].rs].w));
if(rot[H.tre[e.p].ed]) Q.push(PNODE(rot[H.tre[e.p].ed], e.d + H.tre[rot[H.tre[e.p].ed]].w));
}
printf("%d\n", cnt);
}

int main()
{
input();
work();
return 0;
}


# 拓展

k 短路问题还有很多变种，比如不能经过相同节点 k 短路，(可以用第一种方法在一定特征的数据内解决，也可以用 bitset 等记录经过的节点，运用第 2,3 种做法)。

### 3 条评论

#### woc · 2022年12月28日 2:07 下午

nnnnnnnnngggggggggg

#### wdssean · 2021年11月16日 4:36 下午

TQL %%% orzorzorz

orz%%%sto