[SCOI2007 kshort]求图的s-t第K短简单路问题，若有长度相同的，字典序小的优先。
首先，由于是简单路，所以
A*是不能做的，因为有可能有两条s-i（i为某个中间点）路P1和P2，P1比P2短，但由于P1到达的顶点与P2不同，导致最终沿P1到达t的路径长度长于沿P2到达t的（甚至有可能沿P1根本到不了t）。然后，如果直接用DFS，由于要求的是第K优解，而不是最优解，所以不能使用最优性剪枝（包括分支限界），因此专门为最优性剪枝服务的“改变搜索顺序”技巧也不能使用了，因此，能够使用的只有可行性剪枝，而本题的数据范围使得这种算法必然TLE。
正解是一种由迭代加深思想扩展得到的“
迭代变优”DFS。设置一个路径长度上限Z，搜索s到t的所有简单路，在搜索过程中，遇到长度大于Z的路径就停止（剪枝），然后，若得到路径不足K条，则增加Z的值，重新开始搜索，直到得到的路径总数大于等于K条为止。这里可以进行启发式的优化，设g[i]为点i到t的最短路长度，则搜索过程中，假设目前搜到点i，则（目前路径长度+g[i]）是对整条路径最短长度的乐观估计，如果这个值超过了Z，就可以剪枝，但在剪枝之前要记下这个超过了Z的启发值，取其中最小的作为下一次迭代的Z值。那么对于字典序肿么办？可以在搜索过程中，强制先搜编号小的结点，这样得到的s-t路径必然是字典序递增的。另外只要求出第K条路径，搜索就可以终止，因为容易证明，题目要求的第K短的路径一定已经求出来了（只不过不一定是最后一条而已），找到即可。此外，在搜索过程中不要忘了可行性剪枝，就是如果沿目前搜到的路径已经到不了t了，剪枝。
“迭代变优”DFS，就是设置一个解的评价值的上限（最小值）或下限（最大值），在搜索过程中，如果实际评价值（或者启发值，如果可以加启发式优化的话）越过这个限制，则剪枝。在一次搜索后，如果没有得到符合要求的解，就将该限制值
设为本次搜索过程中越界“越”得最近的那个值，重新开始搜索，直到找到所需要的解或者
发现无解（如果一次搜索中没有发生越界，却仍然没有找到解）为止。其应用主要体现在两个方面：（1）搜索树过深甚至无限深，但所需求的那个解却不深的情况；（2）求第K优解的情况。
代码：
#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;
}