[bzoj1073][SCOI2007]kshort【K短路】

50 阅读 0 评论 33 点赞

我是靠谱客的博主饱满小猫咪，最近开发中收集的这篇文章主要介绍[bzoj1073][SCOI2007]kshort【K短路】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=1073
【题解】
　　重点：我没有cheat
　　题意非常简单，就是求 a a 到 $b$ 的第k大简单路径。普通的A*算法并没有可靠的复杂度保证。这里介绍一种有复杂度保证的Yen算法。
　　先给一个简单的概括：首先求出 a a 到 $b$ 的最短路，加入优先队列中。然后考虑每次将一条最短路上的边删除，然后求出次短路并加入优先队列。重复此操作直到求出第k条路径。
　　具体来讲一下寻找新路径的操作：
　　我们定义偏离节点为从 a a 到 $b$ 可以改变的第一个点。
　　那么从这个点及其之后的节点，我们考虑将它的入边删去。
　　不妨记这个点为 now n o w ,记连向它的点为 pre p r e ，一条边的边权为 votei,j v o t e i , j
　　首先求出每个点到 b b 的距离，记作 $d i s_{i}$ ，然后在 pre p r e 的所有出边中，找到一个点 j j 使得 $v o t e_{p r e, j} + d i s_{j} > v o t e_{p r e, n o w} + d i s_{n o w}$ 且 votepre,j+disj v o t e p r e , j + d i s j 最小。
　　然后将这条路径的偏离节点设为 j j 比将其加入队列。
　　但这样寻找的路径可能会经过重复的点，有一个解决的方案：再求 $d i s$ 时可以将到偏离节点之前的点都设为不可用。
　　时间复杂度 O(K∗N∗M∗logM) O ( K ∗ N ∗ M ∗ l o g M )
【代码】

/* - - - - - - - - - - - - - - -
User :
VanishD
problem :
[bzoj1073]
Points :
K-th shortest road -- Yen algorithm
- - - - - - - - - - - - - - - */
# include <bits/stdc++.h>
# define
ll
long long
# define
inf
0x3f3f3f3f
# define
N
51
# define
K
210
using namespace std;
typedef vector <int>
vt;
int read(){
int tmp = 0, fh = 1; char ch = getchar();
while (ch < '0' || ch > '9'){ if (ch == '-') fh = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9'){ tmp = tmp * 10 + ch - '0'; ch = getchar(); }
return tmp * fh;
}
struct Node{
int vote, id;
vector <int> rd, d;
}now, nex;
struct Edge{
int data, next, vote;
}e[N * N * 2];
vt rd[K], eg[N], vg[N];
priority_queue <Node> hp;
int n, m, k, S, T, dis[N], use[N], tag[N], q[N], head[N], frm[N], place;
set <vt> mp;
void build(int u, int v, int w){
e[++place].data = v; e[place].next = head[u]; head[u] = place; e[place].vote = w;
}
bool operator < (Node x, Node y){
if (x.vote > y.vote) return true;
if (x.vote < y.vote) return false;
for (unsigned j = 0; ; j++){
if (j == y.rd.size() && j != x.rd.size()) return true;
if (j == x.rd.size() && j != y.rd.size()) return false;
if (j == y.rd.size() && j == x.rd.size()){
if (x.id > y.id) return true;
else return false;
}
if (x.rd[j] > y.rd[j]) return true;
if (x.rd[j] < y.rd[j]) return false;
}
}
bool operator < (vt x, vt y){
for (unsigned j = 0; ; j++){
if (j == y.size()) return true;
if (j == x.size()) return false;
if (x[j] > y[j]) return true;
if (x[j] < y[j]) return false;
}
}
void spfa(int T){
memset(dis, inf, sizeof(dis));
dis[T] = 0, q[1] = T;
memset(use, 0, sizeof(use));
int pl = 1, pr = 1; use[T] = true;
while (pl <= pr){
int x = q[(pl++) % n];
for (int ed = head[x]; ed != 0; ed = e[ed].next)
if (tag[e[ed].data] == false){
if (dis[e[ed].data] > dis[x] + e[ed].vote || (dis[e[ed].data] == dis[x] + e[ed].vote && x < frm[e[ed].data])){
dis[e[ed].data] = dis[x] + e[ed].vote;
frm[e[ed].data] = x;
if (use[e[ed].data] == false){
use[e[ed].data] = true;
q[(++pr) % n] = e[ed].data;
}
}
}
use[x] = false;
}
}
bool cmp(int x, int vx, int y, int vy){
return vx < vy || (vx == vy && x < y);
}
int main(){
//
freopen(".in", "r", stdin);
//
freopen(".out", "w", stdout);
n = read(), m = read(), k = read(), S = read(), T = read();
for (int i = 1; i <= m; i++){
int u = read(), v = read(), w = read();
build(v, u, w);
eg[u].push_back(v);
vg[u].push_back(w);
}
spfa(T);
bool flag = true;
nex.id = 0, nex.vote = dis[S];
int p = S, tot = 0;
nex.rd.push_back(S), nex.d.push_back(0);
while (p != T){
nex.rd.push_back(frm[p]);
nex.d.push_back(tot += dis[p] - dis[frm[p]]);
p = frm[p];
}
hp.push(nex);
for (int i = 1; i <= k; i++){
if (hp.size() == 0){
flag = false;
break;
}
now = hp.top();
hp.pop();
rd[i].clear();
for (unsigned j = 0; j < now.rd.size(); j++)
rd[i].push_back(now.rd[j]);
if (mp.find(rd[i]) != mp.end()){
i--;
continue;
}
mp.insert(rd[i]);
/*
for (unsigned j = 0; j < rd[i].size();
j++)
printf("%d%c", rd[i][j], (j == rd[i].size() - 1) ? 'n' : '-');
for (unsigned j = 0; j < rd[i].size();
j++)
printf("%d%c", now.d[j], (j == rd[i].size() - 1) ? 'n' : '-'); */
for (unsigned j = now.id; j < now.rd.size() - 1; j++){
memset(tag, false, sizeof(tag));
for (unsigned t = 0; t <= j; t++) tag[now.rd[t]] = true;
spfa(T);
int u = now.rd[j], v = now.rd[j + 1], mni = 0, mn = inf, np;
for (unsigned t = 0; t < eg[u].size(); t++){
int tmpi = eg[u][t], tmp = dis[eg[u][t]] + vg[u][t] + now.d[j];
if (cmp(v, dis[v] + now.d[j + 1], tmpi, tmp) == true && v != tmpi)
if (cmp(mni, mn, tmpi, tmp) == false)
mni = tmpi, mn = tmp, np = vg[u][t];
}
if (mni != 0){
nex.id = j; nex.vote = mn;
nex.rd.clear();
nex.d.clear();
for (unsigned k = 0; k <= j; k++)
nex.rd.push_back(now.rd[k]), nex.d.push_back(now.d[k]);
int tot = nex.d[j], p = mni;
nex.rd.push_back(p), nex.d.push_back(tot += np);
//
printf("%d", nex.d[1]);
while (p != T){
nex.rd.push_back(frm[p]);
nex.d.push_back(tot += dis[p] - dis[frm[p]]);
p = frm[p];
}
/*
for (unsigned k = 0; k < nex.rd.size(); k++)
printf("%d%c", nex.rd[k], (k == nex.rd.size() - 1) ? 'n' : '-');
for (unsigned k = 0; k < nex.rd.size(); k++)
printf("%d%c", nex.d[k], (k == nex.d.size() - 1) ? 'n' : '-'); */
hp.push(nex);
}
//
printf("n");
}
//
printf("n"); 
}
if (flag == false)
printf("Non");
else for (unsigned i = 0; i < rd[k].size();
i++)
printf("%d%c", rd[k][i], (i == rd[k].size() - 1) ? 'n' : '-');
return 0;
}