赛后填坑系列QAQ
贴代码呀
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string> using namespace std; void setIO(const string& a) {
freopen((a+".in").c_str(), "r", stdin);
freopen((a+".out").c_str(), "w", stdout);
} const int N = + , INF = ~0u>>; int n;
#include<vector>
struct Edge{
int to, w;
Edge(int to = , int w = ) : to(to), w(w) {}
};
vector<Edge> G[N], G2[N]; void AddEdge(int u, int v, int w) {
G[u].push_back(Edge(v, w));
G2[v].push_back(Edge(u, w));
} int dis[N]; #include<queue>
namespace SPFA {
int* d;
bool inq[N];
queue<int> q; void insert(int x, int dis) {
if(d[x] <= dis) return;
d[x] = dis;
if(!inq[x]) q.push(x), inq[x] = ;
} void main(int st, int dis[], const vector<Edge> G[]) {
d = dis;
for(int i = ; i <= n; i++) {
d[i] = INF;
inq[i] = ;
}
insert(st, );
while(!q.empty()) {
int u = q.front(); q.pop(); inq[u] = ;
for(unsigned i = ; i < G[u].size(); i++) {
insert(G[u][i].to, d[u] + G[u][i].w);
}
}
}
} struct Node {
int g, h, v;
Node(int g = , int h = , int v = ) : g(g), h(h), v(v) {}
bool operator < (const Node& rhs) const {
return h > rhs.h;
}
}; namespace A_star {
priority_queue<Node> q;
int inq[N]; int main(int st, int ed, int k) {
if(dis[st] == INF) return -;
if(st == ed) k++; q.push(Node(, + dis[st], st));
while(!q.empty()) {
Node cur = q.top(); q.pop();
int u = cur.v; inq[u]++;
if(inq[ed] == k) return cur.g;
if(inq[u] > k) continue; // mark1 for(unsigned i = ; i < G[u].size(); i++) {
const Edge& e = G[u][i];
q.push(Node(cur.g + e.w, cur.g + e.w + dis[e.to], e.to));
}
}
return -;
}
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif int m, k, st, ed;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w);
} scanf("%d%d%d", &st, &ed, &k); SPFA::main(ed, dis, G2);
printf("%d\n", A_star::main(st, ed, k)); return ;
}