• 题意 - 　求有向图中第k短路(可重复走).

• 思路 - 　 A ∗ 算法的讲解: http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx 　 　本题中 A ∗ 的运用我觉得就是在优化BFS, 队列中的元素(x)我们设有ST[x]表示从起点出发到 x 点已走的路径, EN[x]表示 x 距离终点的最短路径. 则队列中元素按G[x] = ST[x]+EN[x]从小到大排列, 每次取出最小的G[x], 将 x 可以到达的点插入队列中(他们的路径是从 x 走到的, 依靠 G[x] 来更新这些点的G), 直到终点被取出第 k 次时有解(说明找到了 k 种不同路径通向终点). 　EN[x]要用反向边预处理最短路. 　 　细节见代码.

#include<cstdio>
#include<queue>
#include<cstring>
#define ft first
#define sd second
using namespace std;

typedef pair<int, int> pii;
const int N = 1e3 + 5;
const int M = 1e5 + 5;

int TO[M], NXT[M], V[M], HD[N];
int re_TO[M], re_NXT[M], re_V[M], re_HD[N];
int DIS[N], VIS[N];
int n, m;
int sz, re_sz;

struct ASTAR {
	int v, pos;
	bool operator < (const ASTAR &tmp) const {
		return DIS[v] + pos > DIS[tmp.v] + tmp.pos;
	}
};

void add(int x, int y, int v) {
	TO[++re_sz] = y; V[re_sz] = v;
	NXT[re_sz] = HD[x]; HD[x] = re_sz;
}

void re_add(int x, int y, int v) {
	re_TO[++sz] = y; re_V[sz] = v;
	re_NXT[sz] = re_HD[x]; re_HD[x] = sz;
}

void dijkstra(int x) {
	priority_queue<pii, vector<pii>, greater<pii> >Q;
	memset(DIS, 0x3f, sizeof (DIS));
	DIS[x] = 0;
	pii st = make_pair(0, x);
	Q.push(st);
	while (!Q.empty()) {
		pii x = Q.top();
		Q.pop();
		int u = x.sd;
		if (VIS[u]) continue;
		VIS[u] = 1;
		for (int i = re_HD[u]; i; i = re_NXT[i]) {
			int v = re_TO[i];
			if (!VIS[v] && DIS[v] > DIS[u] + re_V[i]) {
				DIS[v] = DIS[u] + re_V[i];
				pii y = make_pair(DIS[v], v);
				Q.push(y);
			}
		}
	}
}

int astar(int x, int y, int k) {
	if (x == y) k ++; //注意起点终点相同时, 一开始只有起点在队列中, 会被多计算一次.
	priority_queue<ASTAR>Q;
	ASTAR st;
	st.v = x; st.pos = 0;
	Q.push(st);
	while (!Q.empty()) {
		ASTAR x = Q.top();
		Q.pop();
		int u = x.v;
		if (u == y) {
			-- k;
			if (!k)
				return x.pos;
		}
		for (int i = HD[u]; i; i = NXT[i]) {
			int v = TO[i];
			ASTAR w;
			w.v = v; w.pos = x.pos + V[i];
			Q.push(w);
		}
	}
	return -1;
}

int main() {
	int x, y, v;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++ i) {
		scanf("%d%d%d", &x, &y, &v);
		add(x, y, v);
		re_add(y, x, v);
	}
	scanf("%d%d%d", &x, &y, &v);
	dijkstra(y);
	if (DIS[x] == 0x3f3f3f3f) {
		printf("%d\n", -1); //注意起点终点不连通的情况
		return 0;
	}
	printf("%d\n", astar(x, y, v));
	return 0;
}