【题目描述】：
跳跳虎在外面玩忘了时间，现在他需要在最短的时间内赶回家。
跳跳虎所在的世界可以抽象成一个含有n个点的图（点编号从1到n），跳跳虎现在在1号点，跳跳虎的家在n号点。
图上一共有m条单向边，通过每条边有固定的时间花费。
同时，还存在q个单向传送通道，传送通道也有其时间花费。
传送通道一般来说比普通的道路更快，但是跳跳虎最多只能使用k次。
跳跳虎想知道他回到家的最小时间消耗是多少。
【输入描述】：
第一行输入4个整数n,m,q,k；
接下来m行，每行3个整数u,v,w，表示u到v，时间花费w的普通道路；
接下来q行，每行3个整数x,y,z，表示x到y，时间花费z的传送通道；
【输出描述】：
输出一行，一个整数表示最小时间消耗，如果无法回家输出-1。
【样例输入】：
5 5 2 1
1 2 1
1 3 2
2 4 2
3 4 3
4 5 4
1 4 1
2 5 1
【样例输出】：
2
【样例说明】：
【时间限制、数据范围及描述】：
时间：1s 空间：256M
30%的数据：1≤n≤500，0≤m,q≤2000，k=0；
另30%的数据：1≤n≤500；0≤m,q≤2000，k=1；
100%的数据：1≤n≤500；0≤m,q≤2000，0≤k≤10^9；
本题直接分层图模板题,注意最多只要建n层图.
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
const int N=50000005,M=50000005,INF=0x3f3f3f3f;
int n,m,s,t,Cnt,vis[N],head[M],q,k,ans=INF;
int dis[N],x[N],d[N],T[N];
bool visit[N];
struct Edge{
int u,v,Next;
int w;
}Edge[M];
void Push(int u,int v,int w){
Edge[++Cnt].Next=head[u];
Edge[Cnt].v=v;
Edge[Cnt].w=w;
head[u]=Cnt;
}
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,cmp> Q;
void dijkstra(){
for(int i=1;i<=n*(k+1);i++){
visit[i]=false;
dis[i]=INF;
}
Q.push(s);
dis[s]=0;
while(!Q.empty()){
int u=Q.top();
Q.pop();
if(visit[u]){
continue;
}
visit[u]=true;
for(int i=head[u];i;i=Edge[i].Next){
int v=Edge[i].v;
if(!visit[v]&&dis[v]>dis[u]+Edge[i].w){
dis[v]=dis[u]+Edge[i].w;
Q.push(v);
}
}
}
return;
}
int main(){
int u,v,w;
scanf("%d%d%d%d",&n,&m,&q,&k);
k=min(n,k);
s=1;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
for(int j=0;j<=k;j++){
Push(u+n*j,v+n*j,w);
}
}
for(int i=1;i<=q;i++){
scanf("%d%d%d",&u,&v,&w);
for(int j=0;j<=k;j++){
Push(u+n*j,v+n*(j+1),w);
}
}
dijkstra();
for(int i=0;i<=k;i++){
ans=min(ans,dis[n+n*i]);
}
if(ans!=INF){
printf("%d\n",ans);
}
else{
printf("-1\n");
}
return 0;
}