首页 > 代码库 > vijos1082丛林探险

vijos1082丛林探险

2024-07-18 06:42:01   223人阅读

                                              P1082丛林探险

描述

东非大裂谷中有一片神秘的丛林，是全世界探险家的乐园，著名黄皮肤探险家BB一直想去试试。正好我国科学家2005年4月将首次对东非大裂谷进行科考，BB决定随科考队去神秘丛林探险。在出发之前，他搜集了国内外有关神秘丛林探险的资料，并绘制成一张地图：该地图上有若干安全点（包括入口点和出口点），并将这些安全点编号为1、2、…、n；如果一个安全点和另一个安全点有一条路直接相通，则用一条边标示；该图是一个连通图（任意两点间有至少一条路径），地图上每条路的长度和走这条路需要耗费的体力都做了标示。

KK行走速度为1，并知道自己体力为K。他想知道根据自己的体力情况能否成功地穿过丛林。

格式

输入格式

第一行两个整数n（<=5000） m（<=40000），分别表示地图上安全点的个数和边的数目；
第2行至第m+1 行每行4个整数x y c d，x、y表示有直接相联边的两个点的编号，c走这条路需要耗费的体力；d表示边的长度；（其中150<=c,d<=300）
第m+2行两个整数s t，分别表示安全的入口点和出口点的编号；
第m+3行一个整数k，表示BB的体力值；（K<10^9）
同一行上的多个数据用空格隔开。

输出格式

一个整数，如果BB能安全地从如入口穿过丛林到达出口，输出最短时间，否则输出-1

样例输入1

4 51 2 2 31 3 3 51 4 7 102 4 4 63 4 2 61 45

样例输出1

11

题解：
刚开始学的时候竟然写了3个spfa，一个来判最短体力是否大于k，一个来判最短时间，然后二分再spfa。。。
现在看起来真是水，只要在spfa的时候多加一个条件：当前体力花费<=k，即可，一次spfa跑完！
代码：
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define maxn 5000+100 7 #define maxm 40000+1000 8 #define inf 1000000000 9 using namespace std;10 struct edge{int go,next,w,c;}e[2*maxm];11 int n,m,k,s,t,tot,q[maxn],d[maxn],c[maxn],head[maxn];12 bool v[maxn];13 void ins(int x,int y,int z,int w)14 {15     e[++tot].go=y;e[tot].c=z;e[tot].w=w;e[tot].next=head[x];head[x]=tot;16 }17 void insert(int x,int y,int z,int w)18 {19     ins(x,y,z,w);ins(y,x,z,w);20 }21 bool spfa()22 {23     for(int i=1;i<=n;++i) d[i]=inf;24     memset(v,0,sizeof(v));25     int l=0,r=1,x,y;q[1]=s;d[s]=0;c[s]=0;26     while(l!=r)27     {28         x=q[++l];if(l==maxn)l=0;v[x]=0;29         for(int i=head[x];i;i=e[i].next)30          if(d[x]+e[i].w<d[y=e[i].go]&&c[x]+e[i].c<=k)31          {32              d[y]=d[x]+e[i].w;33              c[y]=c[x]+e[i].c;34              if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}35          }36     }37     return d[t]!=inf;38 }39 int main()40 {41     freopen("input.txt","r",stdin);42     freopen("output.txt","w",stdout);43     cin>>n>>m;44     int x,y,z,w;45     for(int i=1;i<=m;++i){cin>>x>>y>>z>>w;insert(x,y,z,w);}46     cin>>s>>t>>k;47     if(spfa())cout<<d[t]<<endl;else cout<<"-1"<<endl;48     //for(int i=1;i<=n;++i)cout<<d[i]<<‘ ‘<<c[i]<<‘ ‘<<head[i]<<endl;49     return 0;   50 }
View Code

 































        

            
                
                  
                
                

                    联系

                    我们