专栏首页calmoundZOJ 3620 Escape Time II

ZOJ 3620 Escape Time II

题意:

     从初始房间到达终止房间需要经过一系列的房间,没经过一个房间会得到一个价值,从一个房间到达另一个房间同时需要消耗一定的时间,在规定的时间内从初始到达终止房间          所能达到的最大值是多少

#include<stdio.h>
#include<string.h>
#define INF 99999999
const int MAXN=15;

int mp[MAXN][MAXN];//储存路径以及时间
int vis_room[MAXN];//标记房间是否走过
int vis_edge[MAXN][MAXN];//标记这条路是否走过
int jewel[MAXN];//每个房间的价值
int ans1;//储存最大的价值
int n,m,t;//房间数量,路径数量,规定的时间
int s,e;//初始房间,终止房间
//主要思想房间走过无所谓,路径走过不要再走了
void DFS(int s,int value,int time)
{
    int flag;
    if(value==INF) return;//房间不可达到
    if(s==e && value>ans1) ans1=value;//到达了终点并且价值大,替换
    for (int i=0;i<n;i++)
    {
        flag=0;
        if(mp[s][i]!=INF && vis_edge[s][i]==0 && time+mp[s][i]<=t)//房间可以到达,并且路径没有走过
        { 
            if(vis_room[i]==0)
            {
                flag=1;
                value+=jewel[i];//走过的房间财富不用加
                vis_room[i]=1;
            }
            vis_edge[s][i]=1;
            DFS(i,value,time+mp[s][i]);//房间走过了财富不用加,时间继续加
            //if(i!=初始房间)//这句话有没有无所谓,只是多搜了几步而已,不过也要注意
            if(flag)//若该房间以前走过了,价值就不需要减
            {
                value-=jewel[i];  
                vis_room[i]=0;
            }
            vis_edge[s][i]=0; 
        }
    }
}

int main()
{
    int a,b,c;
    int i,j;
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        ans1=ans2=0;
        memset(vis_room,0,sizeof(vis_room));
        memset(vis_edge,0,sizeof(vis_edge));
        scanf("%d%d",&s,&e);
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                mp[i][j]=INF;    
            for (i=0;i<n;i++)
                scanf("%d",&jewel[i]);
            for (i=0;i<m;i++)
            {
                scanf("%d%d%d",&a,&b,&c);
                mp[a][b]=c;
                mp[b][a]=c;
            }
            vis_room[s]=1;
            //这里是wrong的原因,初始房间不一定是0;
            DFS(s,jewel[s],0);//位置,初始房间财宝价值,所用时间
            printf("%d\n",ans1);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • poj 1019 Number Sequence

    http://poj.org/problem?id=1019 题意:1 12 123 1234 12345 一窜数字 求第n位的数字是什么 分析:拿到题就是不会...

    用户1624346
  • Sicily 8843 Ranking and Friendship

    http://soj.me/8843 题意:几个人想做好朋友,朋友之间相差位置小于等于k,且长度相同 分析;排序,将长度相同的放在一起。若长度相同,第i个人能放...

    用户1624346
  • 堆排序

    #include<stdio.h> void AdjustMinHeap(int *a,int pos,int len) { int temp,chi...

    用户1624346
  • 洛谷P2770 航空路线问题(费用流)

    为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边

    attack
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack
  • 【CodeForces 504A】Misha and Forest

    有n个点,代号分别为0到n-1,然后第i个点有di个相连点,与i 相连的点的XOR sum 为si,求所有的边。

    饶文津
  • 洛谷P1481 魔族密码(LIS)

    attack
  • 你听过算法也是可以贪心的吗?

    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

    用户1332428
  • 【hdu 2544最短路】【Dijkstra算法模板题】

    Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路( Single-Source Shortest Paths, SSSP) , 即从单...

    _DIY
  • AtCoder Beginner Contest 100 完整解题报告

    https://beta.atcoder.jp/contests/abc100/tasks

    海天一树

扫码关注云+社区

领取腾讯云代金券