【問題描述】
給出一個圖G和指定的源點(diǎn)s、匯點(diǎn)t，求圖中從點(diǎn)s到點(diǎn)t的第K短路。
【具體題目】
PKU2449（注意：本題有一個猥瑣之處：不允許空路徑。也就是當(dāng)s等于t時要將K值加1）
【算法】
本題有一種最樸素的辦法：改造Dijkstra，一開始路徑(s, 0)（這里設(shè)路徑(i, l)表示從s到i的一條長度為l的路徑）入隊(duì)。然后，
每次取隊(duì)中長度最短的路徑，該路徑(i, l)出隊(duì)，可以證明，若這是終點(diǎn)為i的路徑第x次出隊(duì)，該路徑一定是圖中從s到i的第x短路（若x>K則該路徑已無用，舍棄）。然后從點(diǎn)i擴(kuò)展，將擴(kuò)展到的路徑全部入隊(duì)。這樣直到終點(diǎn)為t的路徑第K次出隊(duì)即可。
該算法容易實(shí)現(xiàn)（借助priority_queue），但時間復(fù)雜度可能達(dá)到O(MK)，需要優(yōu)化。
優(yōu)化：容易發(fā)現(xiàn)該算法其實(shí)有A*的思想，或者說，該算法
其實(shí)是所有結(jié)點(diǎn)的估價函數(shù)h()值均為0的A*算法。為了優(yōu)化此題，需要將h()值改大。顯然，h(i)值可以設(shè)為
從i到t的最短路徑長度（容易證明它是一致的），然后g(i)=目前結(jié)點(diǎn)代表的路徑長度，f(i)=g(i)+h(i)，然后A*即可。
注意：更改路徑條數(shù)應(yīng)該在出隊(duì)時更改，而不能在入隊(duì)時更改，因?yàn)榭赡茉谠撀窂匠鲫?duì)之前會有新的比它更短的路徑入隊(duì)。
代碼（PKU2449）：
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 1500, MAXM = 150000, INF = ~0U >> 2;
struct edge {
int kk, len, next;
} ed[MAXM], ed2[MAXM];
int n, m, s, t, k_, hd[MAXN], tl[MAXN], hd2[MAXN], tl2[MAXN], h[MAXN], q[MAXN + 1], No[MAXN], res = -1;
bool vst[MAXN];
struct qnode {
int i, g;
};
typedef priority_queue <qnode, vector<qnode> > pq;
pq z;
bool operator< (qnode q1, qnode q2)
{
return q1.g + h[q1.i] > q2.g + h[q2.i];
}
void init()
{
int a0, b0, l0;
scanf("%d%d", &n, &m);
re(i, n) hd[i] = tl[i] = hd2[i] = tl2[i] = -1;
re(i, m) {
scanf("%d%d%d", &a0, &b0, &l0); a0--; b0--;
ed[i].kk = b0; ed[i].len = l0; ed[i].next = -1;
if (hd[a0] == -1) hd[a0] = tl[a0] = i; else tl[a0] = ed[tl[a0]].next = i;
ed2[i].kk = a0; ed2[i].len = l0; ed2[i].next = -1;
if (hd2[b0] == -1) hd2[b0] = tl2[b0] = i; else tl2[b0] = ed2[tl2[b0]].next = i;
}
scanf("%d%d%d", &s, &t, &k_); --s; --t; k_ += s == t;
}
void prepare()
{
re(i, n) {h[i] = INF; vst[i] = 0;} h[t] = 0; vst[t] = 1; q[0] = t;
int i, h0, j, h1;
for (int front=0, rear=0; !(!front && rear == n || front == rear + 1); front == n ? front = 0 : front++) {
i = q[front]; h0 = h[i];
for (int p=hd2[i]; p != -1; p=ed2[p].next) {
j = ed2[p].kk; h1 = h0 + ed2[p].len;
if (h1 < h[j]) {
h[j] = h1;
if (!vst[j]) {vst[j] = 1; if (rear == n) q[rear = 0] = j; else q[++rear] = j;}
}
}
vst[i] = 0;
}
}
void solve()
{
qnode q0; q0.i = s; q0.g = 0; z.push(q0);
re(i, n) No[i] = 0;
int i, d0, j, d1;
while (!z.empty()) {
i = z.top().i; d0 = z.top().g; z.pop();
if (No[i] >= k_) continue;
No[i]++;
if (i == t && No[i] == k_) {res = d0; break;}
for (int p=hd[i]; p != -1; p=ed[p].next) {
j = ed[p].kk; d1 = d0 + ed[p].len;
q0.i = j; q0.g = d1; z.push(q0);
}
}
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}