HDU XYZZY (SPFA最长路有向环+floyd判断连通性)_weixin_30666943的博客-程序员宝宝

 

It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developed Advent-style games for deployment on the Y-Crate. Your job is to test a number of these designs to see which are winnable.
Each game consists of a set of up to 100 rooms. One of the rooms is the start and one of the rooms is the finish. Each room has an energy value between -100 and +100. One-way doorways interconnect pairs of rooms.

The player begins in the start room with 100 energy points. She may pass through any doorway that connects the room she is in to another room, thus entering the other room. The energy value of this room is added to the player's energy. This process continues until she wins by entering the finish room or dies by running out of energy (or quits in frustration). During her adventure the player may enter the same room several times, receiving its energy each time.

 

 

InputThe input consists of several test cases. Each test case begins with n, the number of rooms. The rooms are numbered from 1 (the start room) to n (the finish room). Input for the n rooms follows. The input for each room consists of one or more lines containing:

the energy value for room i
the number of doorways leaving room i
a list of the rooms that are reachable by the doorways leaving room i
The start and finish rooms will always have enery level 0. A line containing -1 follows the last test case.
OutputIn one line for each case, output "winnable" if it is possible for the player to win, otherwise output "hopeless".
Sample Input

5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0
5
0 1 2
20 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
21 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
20 2 1 3
-60 1 4
-60 1 5
0 0
-1

Sample Output

hopeless
hopeless
winnable
winnable

如果碰到环 判断当前环是否可以到达N 

否则跑SPFA 判断 dis[N]是否>0

 

code:

//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 500
int dis[2000];
int mapp[500][500];
int mappp[500][500];
int n;
int ener[400];
queue <int > Q;
int mark[2000];
int cnt[2000];
bool spfa()
{
    Q.push(1);
    for(int i=1;i<=n;i++)
    dis[i]=-100000000,mark[i]=0;
        dis[1]=100;
        mark[1]=1;
    while(Q.size())
    {
        int s=Q.front();
        Q.pop();
        mark[s]=0;
        for(int j=1;j<=n;j++)
        {
            int i=s;
            if(j!=s)
            {
                if(mappp[i][j]&&dis[j]<dis[i]+ener[j]&&dis[i]+ener[j]>0)
                {
                    dis[j]=dis[i]+ener[j];
                    if(!mark[j])
                    {
                        mark[j]=1;
                        Q.push(j);
                        cnt[j]++;
                        if(cnt[j]==n-1)
                        {
                            if(mapp[j][n])
                            {
                                cout<<"winnable"<<endl;
                                return 1;
                            }
                        return 0; 
                        }
                    }
                }
            }
        } 
    }
         return 0;
}
int main()
{
    while(1)
    {
        cin>>n;
        if(n==-1)
        return 0;
        int k;
        int x;    
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            mapp[i][j]=0;
            mappp[i][j]=0;
            ener[i]=0;
            cnt[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>ener[i];
            cin>>k;
            for(int j=1;j<=k;j++)
            {
                cin>>x;
                mapp[i][x]=1;
                mappp[i][x]=1;
            }
        }    
        for(k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if((mapp[i][k]==1)&&(mapp[k][j]==1))
            mapp[i][j]=1;
        }
        if(spfa())
        continue;
        if(!mapp[1][n])
        {
        cout<<"hopeless"<<endl;
        continue;
        }
        if(dis[n]>0)
        cout<<"winnable"<<endl;
        else
        cout<<"hopeless"<<endl;
    }
}

 

转载于:https://www.cnblogs.com/OIEREDSION/p/11266300.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30666943/article/details/99261057

智能推荐

c++ ea 代码 生成_看EA如何生成代码框架_weixin_39916355的博客-程序员宝宝

EA的使用给我们带来了极大的方便,同时,在对EA不断的深入使用过程中,我们也一步步的对其功能有了深层次的了解,这次我学到的新功能,就是通过EA,将类图转换成代码框架,这是如何做到的呢?代码工程设置首先,代码生成是分很多种类别的,为了每次生成代码是都简单方便,我们可以先对一些常规内容进行配置。如,我想将生成的代码设置为C#版的,设置方法:选择“工具”中的“选项”,弹出窗体,继续“代码工程”,设置代码...

有没有亚马逊跨境电商适合用的浏览器排名_候鸟浏览器的博客-程序员宝宝

跨境电商用户最看重的就是浏览器的防关联效果。我以一个用户的角度,大概给大家一个相关防关联浏览器的排名。候鸟浏览器特点:安全、国内最火、亚马逊测评专用、界面简洁易上手这款候鸟浏览器是2021年最新的针对亚马逊测评开发的基于chrome内核的反指纹浏览器,经过我们测试相对起来浏览器来说防关联的安全级别更高。浏览器指纹的修改更彻底,操作起来也比较简单至于怎么使用大家可以去候鸟的官网的帮助页面看一下,个人无限版是499一个月,可以创建无限浏览器环境。可以是适配luminati、911S5等市面上常见的代理,经

Diffie-Hellman算法详细讲解 及用java实现一个基于密钥协商的socket通信_太菜了怎么办?的博客-程序员宝宝_diffiehellman算法实例

diffie-Hellman(DH)算法原理Diffie-Hellman算法是Whitefield Diffie和Martin Hellman在1976年公布的一种秘钥交换算法,它是一种建立秘钥的方法,而不是加密方法,所以秘钥必须和其他一种加密算法结合使用。这种秘钥交换技术的目的在于使两个用户安全的交换一个秘钥一遍后面的报文加密。Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。模型分析1)由消息发送的一方构建密钥,这里由甲方构建密钥。2)由构建密钥的一方向对方公布其公钥

SQlite源码分析-体系结构_diaoju3333的博客-程序员宝宝

体系结构在内部,SQLite由以下几个组件组成:内核、SQL编译器、后端以及附件。SQLite通过利用虚拟机和虚拟数据库引擎(VDBE),使调试、修改和扩展SQLite的内核变得更加方便。所有SQL语句都被编译成易读的、可以在SQLite虚拟机中执行的程序集。SQLite支持大小高达2 TB的数据库,每个数据库完全存储在单个磁盘文件中。这些磁盘文件可以在不同字节顺序的计算机...

C# 获取程序当前文件夹_liehuo123的博客-程序员宝宝_c# 获取当前文件夹

Application.StartupPath     //如何获取当前进程所属程序的文件夹位置   (窗体中使用)( label16.Text=Application.StartupPath;)  Environment.SystemDirectory;         //获取系统目录      Environment.CurrentDirectory;       //获取当

sequence系列之sequence和sequencer_Iam柒年的博客-程序员宝宝_sequence和sequencer

sequence和item发送实例未封装实例如下:class bus_trans extends uvm_sequence_item; //bus item定义 rand int data; `uvm_object_utils_begin(bus_trans) `uvm_field_int(data, UVM_ALL_ON) `uvm_object_utils_end ...endclassclass child_seq extends uvm_sequence; //child_

随便推点

PAT——A1085 Perfect Sequence(two pointer)_ZMST的博客-程序员宝宝

题目链接:#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;int a[100010];int main(){ int n,p; scanf(&quot;%d%d&quot;,&amp;amp;n,&amp;amp;p); for(int i=0;i&amp;lt;n;i++) { scanf(&quot;%d&quot;,&amp;amp;a[i]); ...

数据库MySQL的各种锁以及数据库索引[email protected]@的博客-程序员宝宝

以下这几个链接总结的不错,我先存着留个记录,以后有时间再总结深入理解数据库行锁与表锁细谈数据库表锁和行锁数据库索引部分,我看了看一个B站视频链接,也还没总结~B站数据库索引...

柳神跟我说话了_GuoMengKai的博客-程序员宝宝

开心啊啊啊啊啊啊啊啊啊啊。

最简单的Jsp环境配置及数据库连接调试(Jdk7+Tomcat7+Mysql5.5)_infocarrier的博客-程序员宝宝

这是我看到的最简单的Jsp环境配置,用上述软件版本,傻瓜式安装就是了,根本不用手动设置环境变量什么的。注意:利用下文中的first.jsp例子时,有两点要注意,一是把中文的双引号替换为英文的,在macromedia中很容易看出来,有很多个;二是,数据库的用户名和密码要替换为你自己的。文章出处:http://aircraftinteriorschina.com/archiver/?tid

第二弹!谷歌大脑2017总结下篇:Jeff Dean梳理6大领域研究_RubyBoss的博客-程序员宝宝

https://blog.csdn.net/yH0VLDe8VG8ep9VGe/article/details/79055122量子位 出品 | 公众号 QbitAI传奇一般的Jeff Dean今天发布了谷歌大脑2017总结的第二弹。在这篇总结中,Jeff Dean详细论述了谷歌大脑过去一年的AI应用研究,例如如何将机器学习等技术应用于医疗、机器人、创意、公平等等多个领域。这在...

随机森林算法学习(RandomForest)_木鱼&金鱼的博客-程序员宝宝

随机森林算法学习最近在做kaggle的时候,发现随机森林这个算法在分类问题上效果十分的好,大多数情况下效果远要比svm,log回归,knn等算法效果好。因此想琢磨琢磨这个算法的原理。要学随机森林,首先先简单介绍一下集成学习方法和决策树算法。下文仅对该两种方法做简单介绍(具体学习推荐看统计学习方法的第5章和第8章)。Bagging和Boosting的概念与区别该部分主要学习自:http://www....

推荐文章

热门文章

相关标签