题目：
【题目描述】
跳跳虎在外面出去玩忘了时间，现在他需要在最短的时间内赶回家。
跳跳虎所在的世界可以抽象成一个含有 n 个点的图（点编号从 1 到 n ），跳跳虎现在在 1 号点，跳跳虎的家在 n 号点。
图上一共有 m 条单向边，通过每条边有固定的时间花费。
同时，还存在若干个单向传送通道，传送通道也有其时间花费。
传送通道一般来说比普通的道路更快，但是跳跳虎最多只能使用 k 次。
跳跳虎想知道他回到家的最小时间消耗是多少。
【输入格式】
第一行输入 4 个整数 n,m,q,k 。（ n 表示点数，m 表示普通道路的数量，q 表示传送通道的数量，k 表示跳跳虎最多使用 k 次传送通道）
接下来 m 行每行 3 个整数 u,v,w ，表示有一条从 u 到 v ，时间花费为 w 的普通道路。( 1≤u,v≤n,1≤w≤103 )
接下来 q 行每行 3 个整数 x,y,z ，表示有一条从 x 到 y ，时间花费为 z 的传送通道。( 1≤x,y≤n,1≤z≤103 )
【输出格式】
输出一行一个整数表示最小时间消耗，如果没法回到家输出 -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
【数据规模与约定】
对于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≤109。
思路：
分层建图，定义 dis [ u ][ k ] 表示到结点 u ，共经过 k 条第二类边的最短路。
显然我们可以以 k 为阶段划分状态，然后就划分成了最短路的子问题。
dis [ u ][ k ] 可以转移到 dis [ v ][ k ]（第一类边）和 dis [ v ][ k+1 ]（第二类边）。
然后就可以用 dijkstar 求最短路 求出答案。
标程：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<stack> #include<vector> #include<queue> #include<deque> #include<map> #include<set> using namespace std; #define maxn 1001 #define INF 0x3f3f3f3f int n,m,Q,k; int head[maxn],cnt=0; int d[maxn][maxn<<1]; struct hh { int nex,to,dis,bo;//bo用来判断这条边是否是 }t[maxn<<2]; struct pd//重载（做优先队列用） { int u,num,v;//u起始点，num表示这条边之前已经走过了几条传送边 ，v表示 bool operator < (const pd &a)const { return v>a.v; } }; priority_queue<pd> q; inline void add(int nex,int to,int dis,int bo) { t[++cnt].nex=head[nex]; t[cnt].to=to; t[cnt].dis=dis; t[cnt].bo=bo;//bo为 0 表示普通的路，为 1 表示传送通道 head[nex]=cnt; } inline int read() { int kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } inline void dijkstra()//dijkstra 最短路的双层图模板（和普通最短路模板基本一样） { q.push((pd){1,0,0}); d[1][0]=0; while(!q.empty()) { pd x=q.top();q.pop(); if(x.v!=d[x.u][x.num]) continue; for(int i=head[x.u];i;i=t[i].nex) { int v=t[i].to; if(d[v][x.num+t[i].bo]>x.v+t[i].dis)//最短路 { d[v][x.num+t[i].bo]=x.v+t[i].dis; q.push((pd){v,x.num+t[i].bo,d[v][x.num+t[i].bo]});//存：边权，已走过的传送道路数，距点1 的距离 } } } } int main() { freopen("move.in","r",stdin); freopen("move.out","w",stdout); n=read();m=read();Q=read();k=read(); int x,y,z; for(int i=1;i<=m;i++) { x=read();y=read();z=read(); add(x,y,z,0);//存普通的路 } for(int i=1;i<=Q;i++) { x=read();y=read();z=read(); add(x,y,z,1);//存传送通道 } memset(d,INF,sizeof(d)); dijkstra(); int ans=INF; for(int i=0;i<=min(Q,k);i++) ans=min(ans,d[n][i]); if(ans==INF)//判断是否有路 { printf("-1 ");return 0; } printf("%d ",ans); return 0; }