您的位置: 首页  >  IT文章  >  VIJOS:P1082丛林探险

VIJOS:P1082丛林探险

分类: IT文章 • 2022-03-27 22:04:15

VIJOS: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

输入：

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

输出

11

最短路，多加一个限制条件。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=5005;
const int INF=0x3f3f3f3f;
struct Node{
    int v,dist,w;
    int pow;
    Node(){}
    Node(int v,int dist,int w)
    {
        this->v=v;
        this->dist=dist;
        this->w=w;
    }
};
vector<Node> mp[MAXN];
int n,m;
int d[MAXN],vis[MAXN];
int pow[MAXN];//表示到达该点后还剩多少能量
int power;
void spfa(int s)
{
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        vis[i]=0;
    }
    
    queue<int> que;
    que.push(s);
    vis[s]=1;
    d[s]=0;
    pow[s]=power;
    while(!que.empty())
    {
        int now=que.front();que.pop();
        vis[now]=0;
        for(int i=0;i<mp[now].size();i++)
        {
            Node e=mp[now][i];
            if(d[e.v]>d[now]+e.dist&&pow[now]>=e.w)
            {
                d[e.v]=d[now]+e.dist;
                pow[e.v]=pow[now]-e.w;
                if(!vis[e.v])
                {
                    que.push(e.v);
                    vis[e.v]=1;
                }
            }
        }
    }    
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v,dist,w;
        scanf("%d%d%d%d",&u,&v,&w,&dist);
        mp[u].push_back(Node(v,dist,w));
        mp[v].push_back(Node(u,dist,w));
    }
    int st,gl;
    scanf("%d%d",&st,&gl);
    scanf("%d",&power);
    spfa(st);
    if(d[gl]==INF)
        printf("-1
");
    else
        printf("%d
",d[gl]);
    
    
    return 0;
}    
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 5005;
const int INF = 0x7f7f7f7f;
struct Edge{
    int to, w, dist;
    Edge(){}
    Edge(int to, int w, int dist)
    {
        this->to = to;
        this->w = w;
        this->dist = dist;
    }
};
struct Node{
    int u, cost;
    Node(){}
    Node(int u, int cost)
    {
        this->u = u;
        this->cost = cost;
    }
};
int n, m;
vector<Edge> mp[MAXN];
int d[MAXN], vis[MAXN];
int start, goal,power;
void spfa()
{
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
        vis[i] = 0;
    }
    queue<Node> que;
    que.push(Node(start,0));
    vis[start] = 1;
    d[start] = 0;
    while (!que.empty())
    {
        Node now = que.front(); que.pop();
        int u = now.u;
        vis[u] = 0;
        for (int i = 0; i < mp[u].size(); i++)
        {
            Edge e = mp[u][i];
            if (now.cost + e.w <= power&&d[e.to]>e.dist + d[u])
            {
                d[e.to] = e.dist + d[u];
                if (!vis[e.to])
                {
                    vis[e.to] = 1;
                    que.push(Node(e.to,now.cost+e.w));
                }
            }
        }
    }
    if (d[goal] != INF)
        cout << d[goal];
    else
        cout << -1;
}
int main()
{
//    freopen("C:\Users\11624\Desktop\input.in","r", stdin);
//    freopen("C:\Users\11624\Desktop\output.out","w",stdout);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w, dist;
        cin >> u >> v >> w >> dist;
        mp[u].push_back(Edge(v, w, dist));
        mp[v].push_back(Edge(u, w, dist));
    }
    cin >> start >> goal >> power;
    spfa();
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}

相关推荐