栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 1935 XYZZY

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 1935 XYZZY

#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>#include <queue>#include <limits.h>using namespace std;int n;int map[110][110];int en[110];int SPFA(){queue<int> q;int i,k,max,now,j;int used[110],dis[110],in[110];for(i=1; i<=n; i++)dis[i] = 0;memset(in,0,sizeof(in));memset(used,0,sizeof(used));dis[1] = 100; used[1] = 1;q.push(1); in[1]++;while( !q.empty() ){int x = q.front();q.pop();used[x] = 0;if( in[x] > n ) break;for(i=1; i<=n; i++)if( map[x][i] && dis[i] < dis[x] + en[i] ){dis[i] = dis[x] + en[i];if( !used[i] ){in[i]++;used[i] = 1;q.push(i);}}}while( !q.empty() )q.pop();if( dis[n] > 0 )return 1;else{for(i=1; i<=n; i++)for(j=1; j<=n; j++)for(k=1; k<=n; k++)if( map[j][i] && map[i][k] )map[j][k] = 1;for(i=1; i<=n; i++)if( in[i] > n && map[i][n] && map[1][i] )return 1;}return 0;}int main(){int j,k,i,m,to,ans;int tmp[110][110];while( scanf("%d",&n) != EOF && n != -1 ){memset(map,0,sizeof(map));for(i=1; i<=n; i++){scanf("%d%d",&en[i],&m);while(m--){scanf("%d",&to);map[i][to] = 1;}}ans = SPFA();if( ans )printf("winnablen");elseprintf("hopelessn");}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375559.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号