1598: [Usaco2008 Mar]牛跑步

题意：k短路

---

貌似A*的题目除了x数码就是k短路

$$
f(x) = g(x) + h(x)
$$
$g(x)$为到达当前状态实际代价，$h(x)$为当前状态到目标状态的估计代价，需满足$h(x) \le 到目标状态的实际最小代价$

k短路问题中，\(g(x)\)为当前到x的路径长度，\(h(x)\)为x到终点的最短路

根据dijkstra算法，节点i第k次出优先队列时就是s到i的k短路

但是这个算法可以被n元环卡成\(O(nk)\)，还有一种做法还要写可持久化堆好麻烦不学了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define fir first

#define sec second

const int N = 1005, M = 1e4+5, INF = 1e9+5;

inline int read(){

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m, k, u, v, w, s, t;

namespace I {

	struct edge{int v, ne, w;} e[M];

	int cnt, h[N];

	inline void ins(int u, int v, int w) {

		e[++cnt] = (edge){v, h[u], w}; h[u] = cnt;

	}

	priority_queue<pii, vector<pii>, greater<pii> > q;

	int vis[N];

	void dij(int s, int t, int *d) {

		for(int i=1; i<=n; i++) d[i] = INF, vis[i] = 0;

		d[s] = 0; q.push(make_pair(0, s));

		while(!q.empty()) {

			int u = q.top().sec; q.pop();

			if(vis[u]) continue; vis[u] = 1;

			for(int i=h[u];i;i=e[i].ne) {

				int v = e[i].v;

				if(d[v] > d[u] + e[i].w)

					d[v] = d[u] + e[i].w, q.push(make_pair(d[v], v));

			}

		}

	}

}

int d_t[N];

struct edge{int v, ne, w;} e[M];

int cnt, h[N];

inline void ins(int u, int v, int w) {

	e[++cnt] = (edge){v, h[u], w}; h[u] = cnt;

}

priority_queue<pii, vector<pii>, greater<pii> > q;

int vis[N], ans[105];

void a_star(int s, int t) {

	I::dij(t, s, d_t);

	for(int i=1; i<=n; i++) vis[i] = 0;

	q.push(make_pair(d_t[s], s));

	while(!q.empty()) {

		int u = q.top().sec, d = q.top().fir; q.pop();

		vis[u]++;

		if(u == t) {

			ans[vis[t]] = d;

			if(vis[t] == k) return;

		}

		if(vis[u] <= k) for(int i=h[u];i;i=e[i].ne) {

			int v = e[i].v;

			q.push(make_pair(d - d_t[u] + d_t[v] + e[i].w, v));

		}

	}

}

int main() {

	freopen("in", "r", stdin);

	n=read(); m=read(); k=read(); s=n; t=1;

	for(int i=1; i<=m; i++) u=read(), v=read(), w=read(), I::ins(v, u, w), ins(u, v, w);

	memset(ans, -1, sizeof(ans));

	a_star(s, t);

	for(int i=1; i<=k; i++) printf("%d\n", ans[i]);

}