k短路
cpp
// A* O(kn^2logn)
#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define d0 d_0
#define d1 d_1
#define j0 j_0
#define j1 j_1
#define k0 k_0
#define k1 k_1
#define LL long long
#define LD long double
using namespace std;
int n,m,k,a,b;
struct node{
int v;
LL w;
bool operator < (const node &o)const{
return w>o.w;
}
};
struct dij_node{
int v;
LL w;
bool operator < (const dij_node &o)const{
return w>o.w;
}
};
struct STRING{
char p[50];
int l;
bool operator > (const STRING &o)const{
int cst=min(l,o.l);
for(int i=0;i<cst;++i){
if(p[i]>o.p[i]) return 1;
else if(p[i]<o.p[i]) return 0;
}
if(l>=o.l) return 1;
}
};
struct point{
int v;
LL g,h;
STRING s;
LL S;
bool operator < (const point &o)const{
if((g+h)^(o.g+o.h)) return g+h>o.g+o.h;
return s>o.s;
}
};
vector<node> G[60],G2[60];
char inc[60];
int decc[128];
char incode_int(int x){
return (x<=26 ? 'A'+x-1 : 'a'-26+x-1);
}
int decode_char(char x){
return (x>='A' && x<='Z' ? x-'A'+1 : x-'a'+27);
}
LL dis[60];
bool f[60];
const LL mex=1e15;
void dijkstra(int s,LL SSS){ // Part 1 部分
for(int i=1;i<=n;++i) dis[i]=mex;
dis[s]=0;
memset(f,0,sizeof(f));
priority_queue<dij_node> q;
q.push({s,0});
while(q.size()){
dij_node dt=q.top();
q.pop();
if(f[dt.v]) continue;
int x=dt.v;
f[x]=1;
for(int i=0;i<(int)G2[x].size();++i){
int u=G2[x][i].v;
if(SSS&(1LL<<u)) continue;
LL w=G2[x][i].w;
if(dis[u]>dis[x]+w){
dis[u]=dis[x]+w;
q.push({u,dis[u]});
}
}
}
return ;
}
int cnt[60];
void Astar(int s,int t,int k){
memset(cnt,0,sizeof(cnt));
priority_queue<point> q;
STRING psh;
psh.p[psh.l++]=incode_int(s);
q.push({s,0,0,psh,1LL<<s});
while(q.size()){
point dt=q.top();
q.pop();
int x=dt.v;
++cnt[x];
if(x==t && cnt[x]==k){
int len=dt.s.l;
cout<<decc[dt.s.p[0]];
for(int i=1;i<len;++i) cout<<"-"<<decc[dt.s.p[i]];
cout<<"\n";
exit(0);
}
dijkstra(t,dt.S);
for(int i=0;i<(int)G[x].size();++i){
int u=G[x][i].v;
LL w=G[x][i].w;
if(dt.S&(1LL<<u)) continue;
dt.s.p[dt.s.l++]=inc[u];
q.push((point){u,dt.g+w,dis[u],dt.s,dt.S|(1LL<<u)});
--dt.s.l;
}
}
cout<<"No\n";
exit(0);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k>>a>>b;
for(int i=1;i<=m;++i){
int u,v;
LL w;
cin>>u>>v>>w;
G[u].push_back({v,w});
G2[v].push_back({u,w});
}
for(int i=1;i<=52;++i) inc[i]=incode_int(i);
for(int i=0;i<128;++i) decc[i]=decode_char((char)i);
dijkstra(b,0);
if(dis[a]>=mex) cout<<"No\n",exit(0);
Astar(a,b,k);
return 0;
}
// O(n^3k)
#include<cstdio>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp>
#include<bitset>
#include<stack>
#include<cstring>
namespace Use {
using std::vector;
using std::min;
using std::max;
using __gnu_pbds ::priority_queue;
using std::bitset;
using std::stack;
bool operator <(const vector<int>&a, const vector<int>&b) {
unsigned sx = a.size(), sy = b.size(), siz = min(sx, sy);
for (unsigned i = 0; i < siz; ++i)
if (a[i] > b[i]) return 0;
else if (a[i] < b[i]) return 1;
return sx < sy;
}
bool operator >(const vector<int>&a, const vector<int>&b) {
unsigned sx = a.size(), sy = b.size(), siz = min(sx, sy);
for (unsigned i = 0; i < siz; ++i)
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return 0;
return sx > sy;
}//保证字典序的途径
}
using namespace Use;
typedef long long ll;
const int maxn = 55, maxm = 2505, inf = 0x3f3f3f3f;
struct Edge {
int to, dis, next;
} edge[maxm];
int head[maxn], len;
inline void insert(const int &u, const int &v, const int &w) {
edge[++len] = {v, w, head[u]}, head[u] = len;
}
int n, dis[maxn], to;
bitset<maxn>onTheSP;//onTheSP[u] = 1 表示点 u 在最短路上
bitset<maxn>vis;//vis[u] = 1 表示在求最短路时 u 在 close 表上
bitset<maxm>isErased;//isErased[i] = 1 表示有向边 i 被删除了
stack<int>s;// 算出最短路时经过的点的栈，满足 LIFO，辅助求最短路路径
struct Path {
int start;//路径的起始点
int len;//当前将算出的最短路长度
int lastplace;//已经走过的属于前缀的点个数
int lastlen;//已经走过的前缀的长
vector<int>path;//当前将算出的最短路路径
vector<int>erasedEdges;//已经被删去的边
Path (const int &_s = 0) : start(_s), len(0), lastplace(0), lastlen(0) {
path.clear(), erasedEdges.clear();
}
void Init(const int &_s) {
start = _s, len = lastplace = lastlen = 0, path.clear(), erasedEdges.clear();
}
bool operator <(const Path &b) const & {
return len == b.len ? path > b.path : len > b.len;
}//堆使得 < 反向
bool Dijkstra() {
for (int i = 1; i <= n; ++i) dis[i] = inf;//路径初始
isErased.reset();
onTheSP.reset();
vis.reset();
dis[start] = 0;
for (int i = 0, k = lastplace = path.size(); i < k; ++i) vis[path[i]] = 1;
for (int i : erasedEdges) isErased[i] = 1;
for (; !s.empty(); s.pop());
for (int __ = 1, u, w; __ <= n; ++__) {//跑 Dijkstra
u = 0;
w = inf;
for (int i = 1; i <= n; ++i) if (!vis[i] && w > dis[i]) w = dis[i], u = i;
if (!u || w == inf) break;
vis[u] = 1;
s.push(u);
for (int i = head[u], v, d; i; i = edge[i].next)
if (!isErased[i] && dis[v = edge[i].to] > (d = w + edge[i].dis))
dis[v] = d;
}
if (!vis[to] || dis[to] == inf) return 0;// 判断从点 start 开始能不能到达终点 to
for (onTheSP[to] = 1; !s.empty(); s.pop()) //找到全部的在当前最短路上的点
for (int u = s.top(), i = head[u], w = dis[u], v, d; i; i = edge[i].next)
if (!isErased[i] && onTheSP[v = edge[i].to] && dis[v] == (d = w + edge[i].dis)) {
onTheSP[u] = 1;//通过判断能否松弛下一条边判断是否在最短路
break;
}
for (int u = start, w; u != to; ) {
path.emplace_back(u), w = dis[u];
for (int i = head[u], v = (u = n + 1, 0); i; i = edge[i].next)
if (!isErased[i] && onTheSP[v = edge[i].to] && dis[v] == w + edge[i].dis)
u = min(u, v);//保证字典序
}
path.emplace_back(to);
len = lastlen + dis[to];//合并之前的路径前缀
return 1;
}
void Write() {
for (int u : path) printf("%d%c", u, u == to ? 10 : '-');
}
} U, V;
int k, start;
priority_queue<Path>h;
void kthShortestPath() {
if ((U = {start}).Dijkstra()) h.push(U);
for (int siz, u, v, w, e; !h.empty() && --k; ) {
U = h.top();
h.pop();
siz = U.path.size() - 1;//减掉 1 保证不走到终点 to
w = U.lastlen;//直接从上一次走到的前缀的最后点开始走
for (int p = U.lastplace/*同理*/; p < siz; ++p) {
u = U.path[p];
v = U.path[p + 1];
for (e = head[u]; e; e = edge[e].next) if (edge[e].to == v) break;//取出边 e
V.Init(u);//使路径以点 u 为起点
V.erasedEdges = U.erasedEdges;//加入已经不能走的边
V.erasedEdges.emplace_back(e);//去除边 e
V.lastlen = w;//记录已走路径前缀
w += edge[e].dis;//之后路径前缀长增加了 edge[e].dis
for (int i = 0; i < p; ++i) V.path.emplace_back(U.path[i]);//加入已走的点
if (V.Dijkstra()) h.push(V);//在这些条件下，试图扩展路径并入队
}
}
if (h.empty()) printf("No");
else U = h.top(), U.Write();
}
int main() {
int m;
scanf("%d%d%d%d%d", &n, &m, &k, &start, &to);
for (int u, v, w; m; --m) scanf("%d%d%d", &u, &v, &w), insert(u, v, w);
kthShortestPath();
return 0;
}