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

tyvj 丛林探险

2024-10-17 09:30:39   212人阅读

描述

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

4 5
1 2 2 3
1 3 3 5
1 4 7 10
2 4 4 6
3 4 2 6
1 4
5

样例输出1

11

限制

各个测试点1s

建边时，建立时间和体力的双权边，spfa时当时间和体力两个条件同时满足时才入队：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>

using namespace std;//n（<=5000） m（<=40000）
const int N=10010;
const int Maxn=999999999;

int head[N];
int now=1;
int distim[N];
int disene[N];
bool vis[N];
int n,m,start,endd,k;
struct node{
    int u,v,tim,ene,nxt;
}E[N<<3];
queue<int>q;

inline int read()
{
    int x=0;char c=getchar();
    while(c<‘0‘||c>‘9‘)c=getchar();
    while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();
    return x;
}

inline void add(int u,int v,int ene,int tim)
{
    E[now].v=v;
    E[now].ene=ene;
    E[now].tim=tim;
    E[now].nxt=head[u];
    head[u]=now++;
}

inline void spfa(int start)
{
    for(int i=1;i<=n;i++)
        distim[i]=disene[i]=Maxn;//体力允许，tim最少
        
    distim[start]=0;
    disene[start]=0;
    vis[start]=1;
    q.push(start);
    
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        vis[top]=0;
        for(int i=head[top];~i;i=E[i].nxt)
            if(distim[E[i].v]>distim[top]+E[i].tim&&disene[top]+E[i].ene<=k)
            {
                distim[E[i].v]=distim[top]+E[i].tim;
                disene[E[i].v]=disene[top]+E[i].ene;
                if(!vis[E[i].v])
                    vis[E[i].v]=1,
                    q.push(E[i].v);
            }
    }
}

int main()
{
    n=read(),m=read();
    
    for(int i=1;i<=n;i++)
        head[i]=-1;
         
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),ene=read(),tim=read();
        add(u,v,ene,tim);
        add(v,u,ene,tim);
    }
    
    start=read();
    endd=read();
    k=read();
    spfa(start);
    
    if(distim[endd]==Maxn)
        printf("-1");
    else
        printf("%d",distim[endd]);
    return 0;
}

 

tyvj 丛林探险


联系
我们