UOJ #595. 跳跳虎回家

【题目描述】：

跳跳虎在外面玩忘了时间，现在他需要在最短的时间内赶回家。

跳跳虎所在的世界可以抽象成一个含有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;
}