我来水个题解 使用astar算法，先算出dist[ n ] (直接宽搜每个点到终点的距离) astar: 估值为(x + dist[x]) x为当前值 代码(main里有防抄_已取消_): 代码：
#include <cstring> #include <iostream> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int> PII; typedef pair<int, PII> PIII; const int N = 1010, M = 200010; //information int n, m, S, T, K; int h[N], rh[N], e[M], w[M], ne[M], idx; int dist[N]; int st[N]; //into void add(int h[], int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } //a* void dijkstra() { priority_queue<PII, vector<PII>, greater<PII> > heap; heap.push({ 0, T }); memset(dist, 0x3f, sizeof dist); dist[T] = 0; while (heap.size()) { PII t = heap.top(); heap.pop(); int ver = t.y; if (st[ver]) continue; st[ver] = true; for (int i = rh[ver]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({ dist[j], j }); } } } } int astar() { priority_queue<PIII, vector<PIII>, greater<PIII> > heap; heap.push({ dist[S], {0, S} }); memset(st, 0, sizeof st); while (heap.size()) { PIII t = heap.top(); heap.pop(); int ver = t.y.y, distance = t.y.x; st[ver] ++; if (ver == T && st[ver] == K) return distance; for (int i = h[ver]; ~i; i = ne[i]) { int j = e[i]; heap.push({ distance + w[i] + dist[j], {distance + w[i], j} }); } } return -1; } //main int main() { cin >> n >> m; memset(h, -1, sizeof h); memset(rh, -1, sizeof rh); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; add(h, a, b, c); add(rh, b, a, c); } cin >> S >> T >> K; //I don't understand it I just follow others... if (S == T) ++K; dijkstra(); //Don't just copy! cout << astar(); return 0; }