1082

描述

东非大裂谷中有一片神秘的丛林，是全世界探险家的乐园，著名黄皮肤探险家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

样例输入1

Copy

样例输出1

Copy

限制

各个测试点1s

要求输出最小时间，可以在SPFA判断时加一个目前消耗体力<总体力

 #include <cstdio>

 #include <queue>

 #define min(a,b) (a<b?a:b)

 #define INF (1<<30)

 using namespace std;

 const int M(+);

 const int N(+);

 int n,m,u,v,ups,dis,s,t,tps;

 int head[N],sumedge;

 struct Edge

 {

     int u,v,wp,wd,nx;

     Edge(int u=,int v=,int nx=,int wp=,int wd=):

         u(u),v(v),nx(nx),wp(wp),wd(wd){}

 }edge[M<<];

 void ins(int u,int v,int wp,int wd)

 {

     edge[++sumedge]=Edge(u,v,head[u],wp,wd);

     head[u]=sumedge;

 }

 queue<int>que;

 int needp[N],needt[N],inq[N];

 void SPFA()

 {

     for(int i=;i<=n;i++)

         needp[i]=needt[i]=INF;

     que.push(s);inq[s]=;

     needp[s]=;needt[s]=;

     while(!que.empty())

     {

         u=que.front();

         que.pop();

         inq[u]=;

         for(int i=head[u];i;i=edge[i].nx)

         {

             v=edge[i].v;

             if(needt[v]>needt[u]+edge[i].wd&&needp[u]+edge[i].wp<=tps)

             {

                 needt[v]=needt[u]+edge[i].wd;

                 needp[v]=needp[u]+edge[i].wp;

                 if(!inq[v])

                     que.push(v),inq[v]=;

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d%d%d",&u,&v,&ups,&dis);

         ins(u,v,ups,dis);ins(v,u,ups,dis);

     }

     scanf("%d%d%d",&s,&t,&tps);

     SPFA();

     if(needp[t]==INF) printf("-1");

     else printf("%d",needt[t]);

     return ;

 }

巴特西

Vijos——T 1082 丛林探险

https://vijos.org/p/1082

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

最新文章

热门文章