看了这里 http://blog.csdn.net/acm_cxlove/article/details/8679230的分析之后自己又按照自己的模板写了一遍，算是对spfa又加深了一步认识（以前真是只会用，没想太多）。
又来当一次搬运工，一点点进步。
题意是这样的：A个村庄，B个城堡，共有K次穿越的机会，且不能经过城堡或者穿越距离必须不超过L，否则必须停下来，当然，不能再道路中间停下来。
按照大大的思路是这样做的：对于每出队的一个结点u，均有两种方式继续走下去，一中是使用一次穿越，另一种是不使用。这样对于使用穿越的情况，必须考虑所有满足d[u][v]<=L的点v，然后dp[v][k+1] = min(dp[v][k+1],dp[u][k])转移方程,其中dp[u][k]表示从起点A+B走到u使用k次穿越经过的最小距离；对于不使用穿越的情况就和普通spfa一样转移。
然后怎样判断由一个节点到另一个节点能够满足d[u][v]<=L呢，这中间会涉及到城堡不能穿越，可以求出使用spfa求出（i，j）之间的最短距离，对于j是城堡的时候就不把j入队，这样中间有城堡的两个节点d[i][j]是不能直接穿越的，也就是d[i][j] == inf.
然后下面是我写的代码：
（思路也可以去原po那里看）
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pb push_back
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<int>:: iterator IT;
#define N 2000
#define INF 200000
struct EDGE
{
int i, c;
EDGE *ani,*next;
} *Edge[N], E[INF];
int d[N][N], inq[N], dp[N][];
int cnt, A, B, M, L, K;
void add(int i, int j, int c, EDGE &e1, EDGE &e2)
{
e1.i = j, e1.c = c, e1.ani = &e2, e1.next = Edge[i], Edge[i] = &e1;
e2.i = i, e2.c = c, e2.ani = &e1, e2.next = Edge[j], Edge[j] = &e2;
cnt += ;
}
void init(void)
{
cnt = ;
memset(Edge, , sizeof(Edge));
// memset(d, 0x0f, sizeof(d));
}
void preprocess(void)
{
memset(d, 0x3f, sizeof(d));
for(int i = ; i <= A + B; i++)
{
queue<int> q;
memset(inq, , sizeof(inq));
inq[i] = ;
d[i][i] = ;
q.push(i);
while(!q.empty())
{
int u = q.front();
int v;
q.pop();
inq[u] = ;
for(EDGE * p = Edge[u]; p; p = p->next)
if(d[i][v = p->i] > d[i][u] + p->c)
{
if(d[i][v] = d[i][u] + p->c, v <= A && !inq[v])
inq[v] = , q.push(v);
}
}
}
}
void spfa(int s, int end)
{
memset(dp, 0x3f, sizeof(dp));
memset(inq, , sizeof(inq));
queue<int> q;
inq[s] = ;
dp[s][] = ;
q.push(s);
while(!q.empty())
{
int u = q.front(), v;
q.pop();
inq[u] = ;
for(EDGE *p = Edge[u]; p; p = p->next)
for(int k = ; k <= K; k++)
if(dp[u][k] < inf)
{
if(dp[v = p->i][k] > dp[u][k] + p->c)
if(dp[v][k] = dp[u][k] + p->c, !inq[v])
inq[v] = , q.push(v);
if(k - K)
{
for(v = ; v <= A + B; v++)
// if(dp[u][k] < inf)
if(d[u][v] <= L && dp[u][k] < dp[v][k+])
if(dp[v][k+] = dp[u][k], !inq[v])
inq[v] = , q.push(v);
}
}
}
}
int main(void)
{ int T;
for(int t = scanf("%d", &T); t <= T; t++)
{
init();
scanf("%d%d%d%d%d", &A, &B, &M, &L, &K);
for(int i = ; i <= M; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w, E[cnt], E[cnt + ]);
}
preprocess();
spfa(A+B, );
int ans = inf;
for(int k = ; k <= K; k++)
ans = min(dp[][k], ans);
printf("%d\n", ans);
}
return ;
}