[SCOI2007 kshort]求圖的s-t第K短簡(jiǎn)單路問題，若有長(zhǎng)度相同的，字典序小的優(yōu)先。
首先，由于是簡(jiǎn)單路，所以
A*是不能做的，因?yàn)橛锌赡苡袃蓷ls-i（i為某個(gè)中間點(diǎn)）路P1和P2，P1比P2短，但由于P1到達(dá)的頂點(diǎn)與P2不同，導(dǎo)致最終沿P1到達(dá)t的路徑長(zhǎng)度長(zhǎng)于沿P2到達(dá)t的（甚至有可能沿P1根本到不了t）。然后，如果直接用DFS，由于要求的是第K優(yōu)解，而不是最優(yōu)解，所以不能使用最優(yōu)性剪枝（包括分支限界），因此專門為最優(yōu)性剪枝服務(wù)的“改變搜索順序”技巧也不能使用了，因此，能夠使用的只有可行性剪枝，而本題的數(shù)據(jù)范圍使得這種算法必然TLE。
正解是一種由迭代加深思想擴(kuò)展得到的“
迭代變優(yōu)”DFS。設(shè)置一個(gè)路徑長(zhǎng)度上限Z，搜索s到t的所有簡(jiǎn)單路，在搜索過(guò)程中，遇到長(zhǎng)度大于Z的路徑就停止（剪枝），然后，若得到路徑不足K條，則增加Z的值，重新開始搜索，直到得到的路徑總數(shù)大于等于K條為止。這里可以進(jìn)行啟發(fā)式的優(yōu)化，設(shè)g[i]為點(diǎn)i到t的最短路長(zhǎng)度，則搜索過(guò)程中，假設(shè)目前搜到點(diǎn)i，則（目前路徑長(zhǎng)度+g[i]）是對(duì)整條路徑最短長(zhǎng)度的樂觀估計(jì)，如果這個(gè)值超過(guò)了Z，就可以剪枝，但在剪枝之前要記下這個(gè)超過(guò)了Z的啟發(fā)值，取其中最小的作為下一次迭代的Z值。那么對(duì)于字典序腫么辦？可以在搜索過(guò)程中，強(qiáng)制先搜編號(hào)小的結(jié)點(diǎn)，這樣得到的s-t路徑必然是字典序遞增的。另外只要求出第K條路徑，搜索就可以終止，因?yàn)槿菀鬃C明，題目要求的第K短的路徑一定已經(jīng)求出來(lái)了（只不過(guò)不一定是最后一條而已），找到即可。此外，在搜索過(guò)程中不要忘了可行性剪枝，就是如果沿目前搜到的路徑已經(jīng)到不了t了，剪枝。
“迭代變優(yōu)”DFS，就是設(shè)置一個(gè)解的評(píng)價(jià)值的上限（最小值）或下限（最大值），在搜索過(guò)程中，如果實(shí)際評(píng)價(jià)值（或者啟發(fā)值，如果可以加啟發(fā)式優(yōu)化的話）越過(guò)這個(gè)限制，則剪枝。在一次搜索后，如果沒有得到符合要求的解，就將該限制值
設(shè)為本次搜索過(guò)程中越界“越”得最近的那個(gè)值，重新開始搜索，直到找到所需要的解或者
發(fā)現(xiàn)無(wú)解（如果一次搜索中沒有發(fā)生越界，卻仍然沒有找到解）為止。其應(yīng)用主要體現(xiàn)在兩個(gè)方面：（1）搜索樹過(guò)深甚至無(wú)限深，但所需求的那個(gè)解卻不深的情況；（2）求第K優(yōu)解的情況。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 51, MAXK = 201, MAXM = 3000, INF = ~0U >> 2;
struct edge {
int a, b, w, pre, next;
} E[MAXM + MAXN], E0[MAXM + MAXN];
struct edge0 {
int a, b, w;
bool operator< (edge0 e0) const {return b < e0.b;}
} _E[MAXM];
int n, m, s, t, K, dist[MAXN], Q[MAXN + 1];
int Z, Z0, vst0[MAXN], _FL, len0, X00[MAXN], No, len[MAXK], X0[MAXK][MAXN], sum0[MAXK], reslen, res[MAXN];
bool vst[MAXN], res_ex = 0;
void init_d()
{
re(i, n) E[i].pre = E[i].next = E0[i].pre = E0[i].next = i; m = n;
}
void add_edge(int a, int b, int w)
{
E[m].a = a; E[m].b = b; E[m].w = w; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m;
E0[m].a = b; E0[m].b = a; E0[m].w = w; E0[m].pre = E0[b].pre; E0[m].next = b; E0[b].pre = m; E0[E0[m].pre].next = m++;
}
void init()
{
int m0; scanf("%d%d%d%d%d", &n, &m0, &K, &s, &t); init_d(); s--; t--;
re(i, m0) {scanf("%d%d%d", &_E[i].a, &_E[i].b, &_E[i].w); _E[i].a--; _E[i].b--;}
sort(_E, _E + m0);
re(i, m0) add_edge(_E[i].a, _E[i].b, _E[i].w);
}
void prepare()
{
re(i, n) {vst[i] = 0; dist[i] = INF;} vst[t] = 1; dist[t] = 0; Q[0] = t;
int x, y, d0, d1;
for (int front=0, rear=0; !(!front && rear==n || front==rear+1); front==n ? front=0 : front++) {
x = Q[front]; d0 = dist[x];
for (int p=E0[x].next; p != x; p=E0[p].next) {
y = E0[p].b; d1 = d0 + E0[p].w;
if (d1 < dist[y]) {
dist[y] = d1;
if (!vst[y]) {vst[y] = 1; Q[rear==n ? rear=0 : ++rear] = y;}
}
}
vst[x] = 0;
}
}
void dfs(int x, int sum)
{
if (x == t) {
if (sum <= Z) {sum0[No] = sum; len[No] = len0; re(i, len0) X0[No][i] = X00[i]; No++; if (No == K) res_ex = 1;}
else if (sum < Z0) Z0 = sum;
return;
} else {
int h0 = sum + dist[x];
if (h0 > Z) {if (h0 < Z0) Z0 = h0; return;}
vst0[x] = ++_FL; Q[0] = x; int _x, _y;
for (int front=0, rear=0; front<=rear; front++) {
_x = Q[front];
for (int p=E[_x].next; p != _x; p=E[p].next) {
_y = E[p].b;
if (!vst[_y] && vst0[_y] != _FL) {vst0[_y] = _FL; Q[++rear] = _y;}
}
}
if (vst0[t] != _FL) return;
for (int p=E[x].next; p != x; p=E[p].next) {
_y = E[p].b;
if (!vst[_y]) {vst[_y] = 1; X00[len0++] = _y; dfs(_y, sum + E[p].w); if (res_ex) return; else {len0--; vst[_y] = 0;}}
}
}
}
void solve()
{
Z = dist[s]; int No0 = 0; _FL = 0;
while (1) {
Z0 = INF; No = 0; re(i, n) {vst[i] = 0; vst0[i] = 0;}
vst[s] = 1; len0 = 1; X00[0] = s; dfs(s, 0);
if (res_ex) {
No0 = K - No0;
re(i, K) if (sum0[i] == Z) {No0--; if (!No0) {reslen = len[i]; re(j, len[i]) res[j] = X0[i][j];}}
break;
} else if (Z0 == INF) break; else {No0 = No; Z = Z0;}
}
}
void pri()
{
if (res_ex) {
printf("%d", res[0] + 1);
re2(i, 1, reslen) printf("-%d", res[i] + 1);
puts("");
} else puts("No");
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}