题目：

【题目描述】

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

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

接下来 q 行每行 3 个整数 x,y,z ，表示有一条从 x 到 y ，时间花费为 z 的传送通道。( 1≤x,y≤n,1≤z≤10³)

【输出格式】

输出一行一个整数表示最小时间消耗，如果没法回到家输出 -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

【样例输出】

【数据规模与约定】

对于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⁹。

思路：

　　分层建图，定义 dis [ u ][ k ] 表示到结点 u ，共经过 k 条第二类边的最短路。

　　显然我们可以以 k 为阶段划分状态，然后就划分成了最短路的子问题。

　　dis [ u ][ k ] 可以转移到 dis [ v ][ k ]（第一类边）和 dis [ v ][ k+1 ]（第二类边）。

　　然后就可以用 dijkstar 求最短路 求出答案。

标程：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  using namespace std;#define maxn 1001#define INF 0x3f3f3f3fint 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
                  
                    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\n");return 0; } printf("%d\n",ans);return 0;}

转载于:https://www.cnblogs.com/lck-lck/p/9737675.html

你可能感兴趣的文章