/*题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1210
题意大概是:给你一个图,图中有m条边,图上的点由a个乡村和b个城堡构成,标号为1至a为乡村,b至a+b为城堡,最后求从a+b号城堡到1号乡村的最短路,但是走的过程中可以使用魔法靴,魔法靴一次可以瞬间行驶长度为L的路径,最多可以使用k次但是靴子不能穿越城堡,问从a+b点走到1点,最短时间是多少? (1<a+b<=100,L<=500,k<=10)
解题思路:因为100×500×10状态不是很大,直接用dp[i][k][rem]来记录每个点的状态,dp[i][k][rem]表示从源点走到第i个点时魔法靴还可以使用k次,并最近一次用的魔法靴还剩rem长的路劲没走完的最短时间;后面就是一个用bfs实现的最短路的三维spfa算法了,注意更新时的条件就好了;
代码如下:
*/
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 100000000
struct edge
{
int to,c,next;
}edge[21000];
int dp[110][12][510];
int head[110],ant;
void add(int a,int b,int c)
{
edge[ant].to=b;
edge[ant].c=c;
edge[ant].next=head[a];
head[a]=ant++;
}
struct node
{
int n,m,rem;
};
int vis[110][12][510];
void bfs(int s,int k,int l,int e)
{
int i;
node tem,temp;
queue <node> que;
tem.n=s;
tem.m=k;
tem.rem=0;
que.push(tem);
memset(dp[s],0,sizeof(dp[s]));
vis[tem.n][tem.m][tem.rem]=1;
while(!que.empty())
{
tem=que.front();
que.pop();
vis[tem.n][tem.m][tem.rem]=0;
for(i=head[tem.n];i!=-1;i=edge[i].next)
{
temp.n=edge[i].to;
if(tem.rem>=edge[i].c)
{
if(temp.n<=e&&dp[tem.n][tem.m][tem.rem]<dp[temp.n][tem.m][tem.rem-edge[i].c]){
dp[temp.n][tem.m][tem.rem-edge[i].c]=dp[tem.n][tem.m][tem.rem];
temp.m=tem.m;
temp.rem=tem.rem-edge[i].c;
if(!vis[temp.n][temp.m][temp.rem])
{
vis[temp.n][temp.m][temp.rem]=1;
que.push(temp);
}
}
else if(temp.n>e&&dp[tem.n][tem.m][tem.rem]<dp[temp.n][tem.m][0])
{
dp[temp.n][tem.m][0]=dp[tem.n][tem.m][tem.rem];
temp.m=tem.m;
temp.rem=0;
if(!vis[temp.n][temp.m][temp.rem])
{
vis[temp.n][temp.m][temp.rem]=1;
que.push(temp);
}
}
}
if(l>=edge[i].c&&tem.m>0)
{
if(temp.n<=e&&dp[tem.n][tem.m][tem.rem]<dp[temp.n][tem.m-1][l-edge[i].c])
{
dp[temp.n][tem.m-1][l-edge[i].c]=dp[tem.n][tem.m][tem.rem];
temp.m=tem.m-1;
temp.rem=l-edge[i].c;
if(!vis[temp.n][temp.m][temp.rem])
{
vis[temp.n][temp.m][temp.rem]=1;
que.push(temp);
}
}
else if(temp.n>e&&dp[tem.n][tem.m][tem.rem]<dp[temp.n][tem.m-1][0])
{
dp[temp.n][tem.m-1][0]=dp[tem.n][tem.m][tem.rem];
temp.m=tem.m-1;
temp.rem=0;
if(!vis[temp.n][temp.m][temp.rem])
{
vis[temp.n][temp.m][temp.rem]=1;
que.push(temp);
}
}
}
if(dp[tem.n][tem.m][tem.rem]+edge[i].c<dp[temp.n][tem.m][0])
{
dp[temp.n][tem.m][0]=dp[tem.n][tem.m][tem.rem]+edge[i].c;
temp.m=tem.m;
temp.rem=0;
if(!vis[temp.n][temp.m][temp.rem])
{
vis[temp.n][temp.m][temp.rem]=1;
que.push(temp);
}
}
}
}
}
int main()
{
int cas,i,j,t,Min;
int a,b,m,l,k,x,y,c;
scanf("%d",&cas);
while(cas--)
{
ant=0;
memset(head,-1,sizeof(head));
scanf("%d%d%d%d%d",&a,&b,&m,&l,&k);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
for(i=1;i<=a+b;i++)
for(j=0;j<=k;j++)
for(t=0;t<=l;t++){
dp[i][j][t]=inf;
vis[i][j][t]=0;
}
bfs(a+b,k,l,a);
Min=inf;
for(i=0;i<=k;i++)
for(j=0;j<=l;j++)
if(dp[1][i][j]<Min)
Min=dp[1][i][j];
printf("%d\n",Min);
}
return 0;
}