专栏首页Zaqdt_ACMHDU 1317 XYZZY(spfa跑正环)

HDU 1317 XYZZY(spfa跑正环)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1317

       题意是最多有100个房间,从1-n,然后每个房间都有一个能量值(可正可负),每到达一个房间就会获得这个房间的能量值,起点为1,刚开始会有100点能量值,问最后能不能到达n点且到达n点时还有没有能量值。

       样例是多组输入n遇到-1结束,接下来n行中,第一个数表示从第i个房间到其他房间所能获得的能量值,第二个数m表示第i个房间能到达的房间数,然后m个房间编号。

       思路是用spfa去跑最长路,然后在遇到正环的时候我们可以在这个正环里刷能量值,多在环里跑几圈,以至于能量值足够到达n点,其他没什么难点,主要就是跑正环的操作。


AC代码:

#include <bits/stdc++.h>
#define maxn 105
#define inf 105
using namespace std;
struct Node{
	int to,w,next;
	bool operator < (const Node &a) const{
		return a.w < w;
	}
}Edge[maxn * maxn];
int head[maxn * maxn],dist[maxn],cnt[maxn],num;
bool vis[maxn];
int n,m,x,v;

void init(){
	for(int i=1;i<=maxn;i++)
			cnt[i] = 0, head[i] = -1, dist[i] = 0, vis[i] = false;
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].w = w;
	Edge[num].to = v;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void spfa(){
	dist[1] = 100;
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i=head[u];i!=-1;i=Edge[i].next){
			int v = Edge[i].to;
			if(dist[v] < dist[u] + Edge[i].w && cnt[v] < 10000){
				cnt[v] ++;
				dist[v] = dist[u] + Edge[i].w;
				if(vis[v] == false){
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	if(dist[n] > 0){
		puts("winnable");
	}
	else{
		puts("hopeless");
	}
}

int main()
{
	while(~scanf("%d",&n)){
		if(n == -1) break;
		init();
		for(int i=1;i<=n;i++){
			scanf("%d%d",&x,&m);
			for(int j=0;j<m;j++){
				scanf("%d",&v);
				add(i, v, x);
			}
		}
		spfa();
	}
	return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 3259 Wormholes(spfa判负环)

           题意是有n个点,m条边,k个虫洞(权值为负),输入完m条无向边后输入k条有向边,问能不能找到一个点,从这个点出发,最后回到这个点的时候权值是负的(...

    Ch_Zaqdt
  • Oil Deposts(dfs)

    题意就是有一大片地方,让你去找里面有多少片油田(八个方向),我们只需要遍历地图,当找到'@'的时候进行dfs,把搜索到的'@'都变成'*'就好了,然后用一个变量...

    Ch_Zaqdt
  • AcWing 141. 周期 || HDU 1358 Period(KMP循环节)

    AcWing题目链接:https://www.acwing.com/problem/content/description/143/

    Ch_Zaqdt
  • 3411 洪水

    3411 洪水 CodeVS原创  时间限制: 1 s  空间限制: 64000 KB  题目等级 : 青铜 Bronze 题解  查看运行结果 题目描述 De...

    attack
  • Java网络编程的Java流介绍

    网络程序所做的很大一部分工作都是简单的输入输出:将数据字节从一个系统移动到另一个系统。Java的I/O建立于流(stream)之上。输入流读取数据,输出流写入数...

    纪莫
  • AcWing 141. 周期 || HDU 1358 Period(KMP循环节)

    AcWing题目链接:https://www.acwing.com/problem/content/description/143/

    Ch_Zaqdt
  • 出圈子问题

    题目描述: 有n个人围成一圈,按顺序排号 从第一个人开始报数(从1到3报数) 所有报到3的人退出圈子 问最后留下来的是第几个人 我们可以将这个题目...

    指点
  • BZOJ2388: 旅行规划(分块 凸包)

    attack
  • C# 图片识别(支持21种语言)

    图片识别的技术到几天已经很成熟了,只是相关的资料很少,为了方便在此汇总一下(C#实现),方便需要的朋友查阅,也给自己做个记号。 图片识别的用途:很多人用它去破解...

    Java中文社群_老王
  • 图片操作系列 —(2)手势旋转图片

    在上次的文章:图片操作系列 —(1)手势缩放图片功能中,我们已经学会了如何用手势来对图片进行缩放。这次我们继续来看第二个操作,那就是如何用手势来旋转图片。

    青蛙要fly

扫码关注云+社区

领取腾讯云代金券