k短路，顾名思义，由s到t第k短的路径，那么我们该如何解决这个问题？
引子——次短路
次短路：求出从s到t的第二短路径，考虑做法：
首先我们可以直接做出最短路，然后考虑：我们有很多种路径可以走到t，点与点之间由很多边我们没有走，那么我们很容易想到：我们每次松弛操作时都是将点与点最近的走法找到了，那如果我们选择一个第二优秀的走法，不就可以了？
那么考虑：我们需要修改最短路径上的几条边？
直觉是：一条，原因：假设需要修改边\(e_1\)和\(e_2\)可以使答案最优，那很显然：只修改\(e_1\)或者\(e_2\)一定比当前答案更小并且比最短路大。
直接给出代码：
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair
int head[2000005],top;
struct node{
int to,next,dis;
} a[2000005];
int dis1[10005];
int dis2[10005];
void add(int u,int v,int w){
a[++top].next=head[u];
a[top].to=v;
a[top].dis=w;
head[u]=top;
}
void dij(int x){
memset(dis1,0x3f,sizeof(dis1));
memset(dis2,0x3f,sizeof(dis2));
priority_queue >q; dis1[x]=0; q.push(make_pair(0,x)); while(!q.empty( )){ int w=q.top( ).first; int u=q.top( ).second; q.pop( ); if(dis2[u] continue; for(int i=head[u];i!=-1;i=a[i].next){ int v=a[i].to; int cost=w+a[i].dis; if(dis1[v]>cost) swap(dis1[v],cost), q.push( P(dis1[v],v)); if(dis2[v]>cost&&cost>dis1[v]) swap(dis2[v],cost), q.push(P(dis2[v],v)); } } } int main(){ int n,r; scanf("%d%d",&n,&r); memset(head,-1,sizeof(head)); int u,v,w; for(int i=1;i<=r;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dij(1); printf("%d\n",dis2[n]); return 0; } 那么如何引申到k短路呢? 思考——k短路 显然，只修改一条边，做k次肯定不对，原因如下： ， 1 显然当k>e时就做不了了（当然会有这样的K） 2 存在x条次优边的和大于某条此优边 那么我们就需要一些非常bt的算法了 前车之鉴——Solution1 A* 首先我们得有一个类似于博弈的思想：次短路和最短路的不同在于失策一步（即以此非最有决策）。也就是说：你按着最短路向终点走，有一步失误了（毕竟人在河边走，哪有不湿鞋），然后紧接着你按着现在的最短方向走到了终点，那么这条路也许就是次短路。是不是次短路取决于你是哪一步走错了。而这一步，可能会让后续的答案非常非常大！！！！！或者很小。 那么此时，我们需要简单估计出这次失误的影响，来粗略判断它究竟可能时第几小。由此，有了 A*算法的估价函数。 Point 1 用 F(x) 表示以当前的走法走到 x 的距离，H(X) 表示 x 到终点的最短路长度。 --Note 1 那么对于 x 节点，我们下一步可以选择 “走对” 或者 “走错”，于是这一个 x 又可以染色到相邻的节点。 Point 2 每一次我们选择 F(x)+H(X) 最小的 x 节点染色，那么最先到达终点时终点的 F(x) 就是最短路 (很像 dijstra的贪心思想)，那么显然：第二次到达终点就是次短路。 --Note 2 原因： 简而言之，我们的染色方式确保了被染色节点的 F(x)+H(x) 一定是递增的，而到达了终点，H(x)=0，那么 F(x) 就是递增的。（者可以用bfs思想来理解） 这种算法在随机数据下，若边权较小，同时k 较大，速度不如上一迭代加深搜索。但是它的优点是稳定。 PS：由于迭代加深这个算法实在实在太太太bt了，我们......不予赘述（百度，让世界更美好） 时间复杂度 \(O(NKlog_2K)\) 那么作为一个老图伦选手，我们绝壁在想：这中算法就和SPFA一样，肯定可以卡，于是：线索形成思想，然后......以后你做K短路又少了一种满分写法......考虑一种卡 A* 的图：构造一个大环，包含起始节点和终止节点即可。（相信你完全理解） #include #include #include #include #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 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 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); g1.addeg(a,b,c); g2.addeg(b,a,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; } 后车方向盘——Solution2 可持久化可并堆 PS：我们一般用可持久化左偏树，原因：代码比较好些，性质比较优秀，当然，斐波那契堆也是很棒的，但是说实话，考场打这种算法......真的有点顶。言归正传： 其实，可并堆的做法是对 A* 做法的一种改进。 由于 A* 做法可能在多次扩展后才能找到一条路径，浪费时间（等于浪费生命），也使得时间复杂度变得非常大。 如果可以在每次扩展时都能得到一条路径，就可以将时间优化到 \(O(K\log N)\) 这个级别。 怎么做到这样呢？我们先将反图的最短路树建立出来。任何一条 S-T 路径都可以表示为若干树边和非树边交替出现的序列。我们可以直接使用其非树边序列表示这个序列。 现在定义几个东西： dis(x)：x点沿着最短路树走到 T的路径长度。 \(e.s,e.t,e.w\)：非树边 e的起始节点，终止节点和长度。 \(\Delta e\)：从\(e.s\)出发走非树边e，再走最短路，比直接走\(e.s\)的最短路多走的距离 一条路径的长度，可以表示为每条非树边多走的距离之和。即 \(\sum \Delta e\) 如果找到一条合法的路径 \(e_1,e_2,\cdots ,e_m\) ，考虑如何像 A* 算法，找一个比这条路径略长的新的路径。保证每次找到的路径不重复。 很容易：有两种方式可以找到一条新的合法路径，并且这条路径尽可能的短，而且可以保证不重复。 Way 1 将 \(e_m\)替换成一条\(\Delta\)更大的非树边 Way 2 将序列后面添加上一条 \(\Delta\)最小的可行非树边即\(e_1,e_2⋯,e_m,e_{m+1}\) 考虑正确性：将非树边序列映射到一张新的图上。将 \(e_i\)映射为新图的点，如果\(ej⋯ \cdots e_i,e_j\cdots\) 是一个合法的路径 (即 \(e_i.t\) 可以通过树边走到 \(e_j.s\) )，那么 \(e_i\)和\(e_j\)之间存在一条边。现在即：求这张新的图的不规定终点的 k 短路。于是，算法的正确性就非常显然了。 对于所有的非树边序列，只需保存它的\(\sum \Delta e\)以及\(e_m\)即可。每次，从所有的已知的非树边序列中选择\(\sum \Delta e\)最小的那一个作为新的路径，并且从它开始进行扩展，将扩展出的新序列加入已知序列的集合中。已知序列的集合需要用堆 (优先队列) 维护。 接下来就是如何扩展的问题了。先考虑如何找到一条边的所有可行后继非树边。这些边就是所有挂在最短路树上\(e_m.t\cdots T\)上的非树边。也就是说一条边的可行后继非树边集合为 \(e.t\)在最短路树上的父亲的集合并上挂在\(e.t\)上的非树边。由于我们在扩展时寻找的是最小可行非树边，因此将这个集合用可并堆维护，每个点的集合由其父亲的集合继承而来。这样，一条非树边的最小可行后继非树边就是 \(e.t\) 的可并堆的跟。 如何替换一条边呢？一条边所在的可并堆的两个儿子可以替换这条边。 综上，就是 \(O(K\log_2 N)\) 的 K 短路做法。 需要注意几个地方： 当所有的路径找完了，需要及时退出，以免 pop一个空的优先队列。 当图中根本就没有第二条路径，S的可并堆将是空的，这时候需要直接退出。 时间复杂度：\(O(T(shortest path)+nlog_2n+klog_2n)\) 下面是魔法猪学院的代码。（洛谷\(P2483\)） #include #include #include #include #include #include using namespace std; const int N = 5050; const int M = 200050; const int MAXN = 10*M; const double eps = 1e-8; int n,m,fa[N],tot,rt[N],pre[N]; double lim,g[N]; bool vis[N]; struct node{ int ls,rs,dis,tl; double v; }p[MAXN]; int merge(int x,int y){ if(!x||!y)return x+y; if(p[x].v-p[y].v>=eps)swap(x,y); int u = ++tot; p[u] = p[x]; p[u].rs = merge(p[u].rs,y); if(p[p[u].ls].dis p[u].dis = p[p[u].rs].dis+1; return u; } typedef pair int hed[N],cnt=1; bool cov[2*M]; struct edge{ int to,nxt; double w; }e[2*M]; void ae(int f,int t,double w){ e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; hed[f] = cnt; } void dij(){ priority_queue > q; for(int i=1;i q.push(P(0.0,n)); while(!q.empty()){ P tp = q.top(); q.pop(); int u = tp.second; if(vis[u])continue; vis[u] = 1; for(int j=hed[u];j;j=e[j].nxt){ if(j&1){ int to = e[j].to; if(g[to]+eps>g[u]+e[j].w){ g[to] = g[u]+e[j].w; q.push(P(g[to],to)); } } } } } void dfs(int u){ vis[u] = 1; for(int j=hed[u];j;j=e[j].nxt)if(j&1){ int to = e[j].to; if(fabs(g[to]-(e[j].w+g[u]))<=eps&&!vis[to]){ fa[to] = u; cov[j^1] = 1; dfs(to); } } } void topo(){ priority_queue q; for(int i=1;i<=n;i++)q.push(P(g[i],i)); for(int u,i=1;i<=n;i++){ u = q.top().second;q.pop(); if(fa[u])rt[u] = merge(rt[u],rt[fa[u]]); } } int main(){ scanf ("%d%d",&n,&m); scanf("%lf",&lim); int f,t; double w; for(int i=1;i<=m;i++){ scanf ("%d%d",&f,&t); scanf("%lf",&w); ae(f,t,w); ae(t,f,w); } dij(); memset(vis,0,sizeof(vis)); dfs(n); for(int j=2;j<=cnt;j+=2){ if(!cov[j]){ int f = e[j^1].to,t = e[j].to; double w = g[t]+e[j].w-g[f]; p[++tot].v = w,p[tot].dis = 1,p[tot].tl = t; rt[f] = merge(rt[f],tot); } } topo(); priority_queue q; int ans = 0; if(lim+eps>g[1]) lim-=g[1],ans++; if(rt[1])q.push(P(p[rt[1]].v,rt[1])); while(!q.empty()){ P tp = q.top(); q.pop(); if(lim+eps>tp.first+g[1]) lim-=(tp.first+g[1]),ans++; else break; int u = tp.second,ls = p[u].ls,rs = p[u].rs; if(ls) q.push(P(tp.first-p[u].v+p[ls].v,ls)); if(rs) q.push(P(tp.first-p[u].v+p[rs].v,rs)); int t=p[u].tl; if(rt[t]) q.push(P(p[rt[t]].v+tp.first,rt[t])); } printf("%d\n",ans); return 0; } //本代码来自博客 https://www.mina.moe/archives/2777 ，疯狂安利这个博主，写得很很很很好，大赞！ #include #include #include #include #include #include #define MX 200008 #define oo 123123123123123 using namespace std; template 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 void input(){ int a, b; double c; read(N); read(M); scanf("%lf", &E); for(int i=1; i<=M; i++){ read(a); read(b); scanf("%lf", &c); G.addeg(a, b, c); R.addeg(b, a, c); } } 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短路的问题，