JDOJ1259 VijosP1082 丛林探险


题目大意

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

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

 

这道题乍一看感觉像是Surface Book的Dijsktra……

不过越看越不对,越看越不对……Woc这题这么写根本不行啊……因为双重权值要求的不是第一权值最小而是第一权值达到阈值

阈(yù)值,指的是用于标记的临界值(最大值,最小值等),没有“阀值”一词!

于是考虑大型暴力DFS。首先DFS暴力扫图可以解决问题。至于时间复杂度……剪完枝应该……似乎……可以A了吧……

然后就A了。

#include <cstdio>
#include <algorithm>
  
using namespace std;
  
int s,t,k,top,ans=0x7fffffff,n,m,ina,inb,inc,ind,head[5010],to[80010],nex[80010],vala[80010],valb[80010];
  
void addedge(int ta , int tb , int tc , int td)
{
    to[++top] = tb;
    nex[top] = head[ta];
    head[ta] = top;
    vala[top] = tc;
    valb[top] = td;
    return;
}
  
void dfs(int pos , int ta , int tb , int from)
{
    if(ta > k) return;
    if(tb > ans) return;
    if(pos == t)
    {
        ans = min(ans , tb);
        return;
    }
    for(int i = head[pos] ; i ; i = nex[i])
        if(to[i] != from)
            dfs(to[i] , ta + vala[i] , tb + valb[i] , pos);
}
  
int main()
{
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d%d" , &ina , &inb , &inc , &ind);
        addedge(ina,inb,inc,ind);
        addedge(inb,ina,inc,ind);
    }
    scanf("%d%d%d" , &s , &t ,&k);
    dfs(s,0,0,0);
    if(ans == 0x7fffffff) ans = -1;
    printf("%d",ans);
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ1259 VijosP1082 丛林探险


不骗了,不骗了。
A Simple OIer fighting tooth and nail.