/*
题意:从1走到n,每走到一个屋子即可获得屋里的能量。
能量值可为负,问是否可以走到n
思路:
题目实际是求从起点到终点的最长路径问题
由于没到一个点,能量值不为负,所以使用d[]来记录到各点后的能量值
,初始化为0,然后使用循环进行松弛,最后判断d[n]是否大于零,如果
是则可达。但是如果图中出现正环,则可能使程序陷入死循环,则不要
在出现正环时能跳出循环。
另外,在之前需要进行一次初始化,从n开始进行逆向搜索,判断各点
是否能到达n(这一步必不可少,若在不可达的点集中出现一个环则会出错)
,然后使用队列优先的Bellman-Ford算法即可
*/
#include <cstdio>
#include <cstring>
const int nMax=110;
int G[nMax][nMax],w[nMax],d[nMax];
int q[nMax],inq[nMax],inedq[nMax];
int visit[nMax],reach[nMax];
int n;
void dfs(int u)
{
visit[u]=1;
reach[u]=1;
for(int v=1;v<=n;v++)
{
if(G[v][u] && !visit[v])
{
dfs(v);
}
}
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1)
{
if(n==-1)
break;
memset(G,0,sizeof(G));
memset(w,0,sizeof(w));
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
int k;
scanf("%d",&k);
for(int j=0;j<k;j++)
{
int u;
scanf("%d",&u);
G[i][u]=1;
}
}
memset(visit,0,sizeof(visit));
memset(reach,0,sizeof(reach));
dfs(n);
if(!reach[1])
{
printf("hopeless\n");
continue;
}
int front=0,rear=0;
memset(q,0,sizeof(q));
memset(d,0,sizeof(d));
memset(inq,0,sizeof(inq));
memset(inedq,0,sizeof(inedq));
q[front++]=1;
d[1]=100;
inq[1]=1;
inedq[1]++;
bool ok=false;
while(front!=rear)
{
int u=q[rear++];
if(rear==n)
rear=0;
inq[u]=0;
for(int v=1;v<=n;v++)
{
if(G[u][v] && reach[v] && d[u]+w[v]>d[v])
{
d[v]=d[u]+w[v];
if(!inq[v])
{
q[front++]=v;
if(front==n)
front=0;
inq[v]=1;
inedq[v]++;
if(inedq[v]>n)
{
ok=true;
break;
}
}
}
}
if(d[n]>0 || ok)
break;
}
if(d[n]>0 || ok)
printf("winnable\n");
else
printf("hopeless\n");
}
return 0;
}
分享到:
相关推荐
假装你是Xyzzy A Cards Against Humanity克隆,服务器和Web客户端。 有关完整的详细信息,请参见WebContent / license.html。 注意:该项目仅与Tomcat 7一起使用,不支持所有其他版本。 当前,构建PYX的唯一方法是...
缓冲区列表(缓冲区菜单),例如Emacs或xyzzy,可以保存/关闭文档。 特征 显示开幕文件清单 保存和/或关闭标记的文档 配置 像这样添加您的keymap.cson: 'atom-workspace': 'ctrl-x ctrl-b': 'buffer-list:show' ...
>>> packed = msgpack.packb(msgpack.ExtType(42, b'xyzzy')) >>> msgpack.unpackb(packed) ExtType(code=42, data='xyzzy') You can use it with ``default`` and ``ext_hook``. See below. Note for msgpack ...
假装您的度量处理器是Xyzzy。 从Apache Kafka(0.10.1.0或更高版本)中获取度量标准信息,并将其保存到PostgreSQL(9.5或更高版本;使用INSERT ... ON CONFLICT DO NOTHING)。 删除使用者偏移量后可以安全地重新...
ANSI Common Lisp 中但不在 xyzzy 中的一系列计划好的东西。 安装 从网络安装程序 。 如何使用 我会暂时阅读它。 (eval-when (:execute :compile-toplevel :load-toplevel) (require "ansify")) ansify 实现的...
Docker Your Xyzzy启用您的Xyzzy: docker pull emcniece/dockeryourxyzzy : Docker Hub: 支持的标签和相应的Dockerfile链接: latest , 4 ( )什么是Docker Your Xyzzy?这是“卡”克隆的容器化版本。 :warning...
木乃伊类似于拉链的结构: 以易于检索的形式存储从根到所选节点的路径具有统一的内部树结构(每个分支节点中的:children矢量)基本原理我在...用法添加到您的project.clj : [mkremins/xyzzy " 0.3.4 " ]执照。 乱走。
先决条件 节点 npm 口(> = 3.9.0) 安装 npm install 用法 gulp watch serve 转到 特征 ES6(+棉绒) SCSS HTTP服务器 LiveReload
名称 find_open_resolvers -- 在给定的 IP 范围内查找开放的 DNS 解析器。... --fqdn Fully Qualified Domain Name to query for (www.xyzzy.net) --verbose be verbose --help display brief help --man displa
Docker Your Xyzzy 启用您的Xyzzy: docker pull emcniece/dockeryourxyzzy : Docker Hub: 支持的标签和相应的Dockerfile链接: latest , 4 ( ) 什么是Docker Your Xyzzy? 这是“卡”克隆的容器化版本。...
xyzzy.github.io:我的个人博客的Jekyll来源
默认摘要版本配置在xpasswd....digest ( "xyzzy" ) . then ( function ( key ) { console . log ( key ) ; // use Promise chaining to validate the password return validate ( "xyzzy" , key ) ; } ) .
假装你是Xyzzy A Cards Against Humanity克隆,服务器和Web客户端。 有关完整的详细信息,请参见WebContent / license.html。 注意:该项目仅与Tomcat 7一起使用,不支持所有其他版本。 当前,构建PYX的唯一方法是...
var token = xforgot ( { secret : "xyzzy" , salt : "foobar" } ) ; // Send token to user via URL... if ( xforgot . verify ( { token : token , secret : "xyzzy" , salt : "foobar" } ) ) { // Reset the ...
如果你没有进一步了解元字符,可能不懂其中含义,不过没关系,在这里你只要知道,该代码的任务是显示电子邮箱dragon@xyzzy.com,用户名和组织名. Function SubMatchTest(inpStr) Dim oRe, oMatch, oMatches Set oRe = ...
YaTeX在DOS和Windows上的其他杰出编辑器上都有兄弟,Vz,Wz,Hidemaru,xyzzy.如果您使用YaTeX系列,您可以在任何平台上以相同的界面编写您的文档。 yahtml 是一个诚实和明亮的 YaTeX 兼容的主要模式包,用于编写 ...
YaTeX在DOS和Windows上的其他杰出编辑器上都有兄弟,Vz,Wz,Hidemaru,xyzzy.如果您使用YaTeX系列,您可以在任何平台上以相同的界面编写您的文档。 yahtml 是一个诚实和明亮的 YaTeX 兼容的主要模式包,用于编写 ...
使用已实现的作弊功能(xyzzy + Shift + Enter)解决所有WinMine问题。 计算网格的大小并标记所有地雷。
从您最喜欢的编辑器运行Wandbox Vim: : Emacs的: : xyzzy: ://gist.github.com/kikairoya/7544234执照Boost软件许可1.0常问问题如果要添加编译器怎么办? 请求请求到 。如果我想向Wandbox添加功能怎么办?请将...