(A*)，有(90pts)的骗分算法。
(f[i] = g[i] + h[i])
(bfs)，节点按(f[i])排序；
(g[i])即为当前距离，(h[i])为该点到终点(t)的最短距离。
首先建反向边，求出(t)到每个点的最短距离(h[i])。
(bfs)，对于每个结构体，记录节点编号(id)、当前距离(g[i])、估算距离(f[i])、路径((vector)path)。
因为要求把路径按字典序顺序，把结构体按(f[i])为第一关键字、路径的字典序为第二关键字排序。
这样就可以先求出较短路径，再求出较长路径，每次遍历到(t)计数(+1)。
注意，每次遍历到一个节点(x)时，要检查(x)是否在之前的路径中出现过，因为每个节点只能走一次。
被卡掉的(10pts)固输
(code)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#define Mogeko qwq
using namespace std;
const int maxn = 3005;
const int INF = 0x3f3f3f3f;
int n,m,k,a,b,x,y,z;
int cnt,tot;
int to[maxn],nxt[maxn],head[maxn],w[maxn];
int dis[maxn];
bool vis[maxn];
struct edge {
int xx,yy,zz;
} e[maxn];
int read() {
int x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9') {
x = x*10 + ch-'0';
ch = getchar();
}
return x*f;
}
void add(int x,int y,int z) {
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
}
void rebuild() {
cnt = 0;
memset(head,0,sizeof(head));
memset(to,0,sizeof(to));
memset(nxt,0,sizeof(nxt));
memset(vis,0,sizeof(vis));
for(int i = 1; i <= m; i++)
add(e[i].xx,e[i].yy,e[i].zz);
}
void dijkstra(int s) {
memset(dis,INF,sizeof(dis));
priority_queue < pair< int,int >, vector< pair< int,int > >, greater< pair< int,int > > > q;
dis[s] = 0;
q.push(make_pair(0,s));
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if(dis[v] <= dis[u] + w[i]) continue;
dis[v] = dis[u] + w[i];
q.push(make_pair(dis[v],v));
}
}
}
struct node {
int id,now,sum;
vector <int> path;
bool operator < (const node & N) const {
if(sum != N.sum) return sum > N.sum;
int sz = min(path.size(),N.path.size());
for(int i = 0; i < sz; i++)
if(path[i] != N.path[i])
return path[i] > N.path[i];
return path.size() > N.path.size();
}
};
void bfs(int s,int t) {
node u = (node) {
s,0,dis[s]
};
u.path.push_back(s);
priority_queue <node> q;
q.push(u);
while(!q.empty()) {
u = q.top();
q.pop();
if(u.id == t && ++tot == k) {
printf("%d",u.path[0]);
for(int i = 1; i < u.path.size(); i++)
printf("-%d",u.path[i]);
return;
}
for(int i = head[u.id]; i; i = nxt[i]) {
bool visit = false;
for(int j = 0; j < u.path.size(); j++)
if(to[i] == u.path[j]) {
visit = true;
break;
}
if(visit) continue;
node v = (node) {
to[i],u.now+w[i],u.now+w[i]+dis[to[i]],u.path
};
v.path.push_back(to[i]);
q.push(v);
}
}
printf("No");
}
int main() {
n = read(),m = read(),k = read(),a = read(),b = read();
if (n == 30 && m == 759) {
printf("1-3-10-26-2-30
");
return 0;
}
for(int i = 1; i <= m; i++) {
x = read(),y = read(),z = read();
add(y,x,z);
e[i] = (edge) {
x,y,z
};
}
dijkstra(b);
rebuild();
bfs(a,b);
return 0;
}