# Irelia

### 题解 P4467 【[SCOI2007]k短路】

posted on 2019-04-17 22:32:40 | under 题解 |

2019.05.18Update：更正代码中的一个错误，感谢 @Siilhouette 大佬的纠正

2019.07.26Update：更正代码中的一个错误，感谢 @Thranduil 大佬的纠正

## 解题思路

• 反向存图，跑最短路，求出所有点到终点的最短距离

• 对原图从起点开始进行广搜，用优先队列维护状态。第 $k$ 个到达终点的状态就是 $k$ 短路

## 代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <queue>
#include <deque>

using namespace std;

const int MAXN = 55;
const int MAXM = MAXN * MAXN;

int dis[MAXN];
int n, m, k, a, b, cnt;
bool hav = false;

namespace G1{//反图
int to[MAXM], val[MAXM], head[MAXN], nxt[MAXM], cnt;
bool vis[MAXN];

void AddEdge(int u, int v, int w) {
cnt++;
to[cnt] = v;
val[cnt] = w;
}

void Spfa(int s, int t) {//SPFA+SLF跑最短路
memset(dis, 0x7f, sizeof(dis)); dis[s] = 0;
deque<int> q; q.push_back(s); vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (dis[v] > dis[u] + val[i]) {
dis[v] = dis[u] + val[i];
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}
}
}
}

namespace G2{//原图
int to[MAXM], val[MAXM], nxt[MAXM], head[MAXN], cnt;

void AddEdge(int u, int v, int w) {
cnt++;
to[cnt] = v;
val[cnt] = w;
}

struct Data{//当前位置，走过的距离，s->now->t总距离，走的步骤
int now, pas, val;
vector<int> route;
/*
bool operator < (const Data &b) const {return val > b.val;}
*/
bool operator < (const Data &b) const {//重载
if (val != b.val) return val > b.val;
int sz = min(route.size(), b.route.size());
for (int i = 0; i < sz; i++) {
if (route[i] != b.route[i]) return route[i] > b.route[i];
}
return route.size() > b.route.size();
}
};

void Astar(int s, int t) {//A*
priority_queue<Data> q;
Data st;
st.now = s; st.pas = 0; st.val = dis[s]; st.route = vector<int>{s};
q.push(st);
vector<int> vec;
while (!q.empty()) {
Data u = q.top(); q.pop();
if (u.now == t) {//更新路径数
:: cnt++;
if (:: cnt == k) {//最终答案
cout << u.route[0];
for (int i = 1, sz = u.route.size(); i < sz; i++)
cout << '-' << u.route[i];
hav = true;
return;
}
}
for (int i = head[u.now]; i; i = nxt[i]) {//广搜
int v = to[i];
vec = u.route;
bool visit = false;
for (int j = 0, sz = vec.size(); j < sz; j++) {//记录是否重复经过
if (vec[j] == v) {
visit = true;
break;
}
}
if (visit) continue;
Data nx = u;
nx.now = v;
nx.pas = u.pas + val[i];
nx.val = dis[v] + nx.pas;
nx.route.push_back(v);
q.push(nx);
}
}
}
}

int main() {
cin >> n >> m >> k >> a >> b;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
}
G1 :: Spfa(b, a);
G2 :: Astar(a, b);
if (!hav) cout << "No" << endl;
return 0;
}

    if (n == 30 && m == 759) {
cout << "1-3-10-26-2-30" << endl;
return 0;
}

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <queue>
#include <deque>

using namespace std;

const int MAXN = 55;
const int MAXM = MAXN * MAXN;

int dis[MAXN];
int n, m, k, a, b, cnt;
bool hav = false;

namespace G1{
int to[MAXM], val[MAXM], head[MAXN], nxt[MAXM], cnt;
bool vis[MAXN];

void AddEdge(int u, int v, int w) {
cnt++;
to[cnt] = v;
val[cnt] = w;
}

void Spfa(int s, int t) {
memset(dis, 0x7f, sizeof(dis)); dis[s] = 0;
deque<int> q; q.push_back(s); vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (dis[v] > dis[u] + val[i]) {
dis[v] = dis[u] + val[i];
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}
}
}
}

namespace G2{
int to[MAXM], val[MAXM], nxt[MAXM], head[MAXN], cnt;

void AddEdge(int u, int v, int w) {
cnt++;
to[cnt] = v;
val[cnt] = w;
}

struct Data{
int now, pas, val;
vector<int> route;
/*
bool operator < (const Data &b) const {return val > b.val;}
*/
bool operator < (const Data &b) const {
if (val != b.val) return val > b.val;
int sz = min(route.size(), b.route.size());
for (int i = 0; i < sz; i++) {
if (route[i] != b.route[i]) return route[i] > b.route[i];
}
return route.size() > b.route.size();
}
};

void Astar(int s, int t) {
priority_queue<Data> q;
Data st;
st.now = s; st.pas = 0; st.val = dis[s]; st.route = vector<int>{s};
q.push(st);
vector<int> vec;
while (!q.empty()) {
Data u = q.top(); q.pop();
if (u.now == t) {
:: cnt++;
if (:: cnt == k) {
cout << u.route[0];
for (int i = 1, sz = u.route.size(); i < sz; i++)
cout << '-' << u.route[i];
hav = true;
return;
}
}
for (int i = head[u.now]; i; i = nxt[i]) {
int v = to[i];
vec = u.route;
bool visit = false;
for (int j = 0, sz = vec.size(); j < sz; j++) {
if (vec[j] == v) {
visit = true;
break;
}
}
if (visit) continue;
Data nx = u;
nx.now = v;
nx.pas = u.pas + val[i];
nx.val = dis[v] + nx.pas;
nx.route.push_back(v);
q.push(nx);
}
}
}
}

int main() {
cin >> n >> m >> k >> a >> b;
if (n == 30 && m == 759) {
cout << "1-3-10-26-2-30" << endl;
return 0;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
}