计蒜客-闯关游戏
蒜头君在玩一个很好玩的游戏,这个游戏一共有至多 100 个地图,其中地图 1 是起点,房间 n 是终点。有的地图是补给站,可以加 k_i 点体力,而有的地图里存在怪物,需要消耗 k_i 点体力,地图与地图之间存在一些单向通道连接。
蒜头君从 1 号地图出发,有 100 点初始体力。每进入一个地图的时候,需要扣除或者增加相应的体力值。这个过程持续到走到终点,或者体力值归零就会 Game Over。不过,他可以经过同个地图任意次,且每次都需要接受该地图的体力值。
输入格式
第 1 行一个整数 n (n ≤100)。
第 2 ~ n+1 行,每行第一个整数表示该地图体力值变化。接下来是从该房间能到达的房间名单,第一个整数表示房间数,后面是能到达的房间编号。
输出格式
若玩家能到达终点,输出Yes
,否则输出No
。
样例输入
5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0
样例输出
No
并不是只要有正环就能确保一定能到达终点, 有如下2中情况:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
//----------------------------------
// 点权图
// 价值最大路径
const int INF = 0x3f3f3f3f;
const int N = 101;
struct edge {
int v, next;
edge() {}
edge(int _v, int _next) : v(_v), next(_next) {}
} E[N * N];
int p[N];
int eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
E[eid] = edge(v, p[u]);
p[u] = eid++;
}
int value[N];
int w[N];
int cnt[N];
bool vis[N];
queue<int> q;
bool spfa(int s, int n) {
memset(value, 0, sizeof value);
memset(vis, false, sizeof vis);
memset(cnt, 0, sizeof cnt);
value[s] = 100 + w[s];
vis[s] = true;
cnt[s]++;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
if (cnt[u] == n) { //第一次发现点在正环上, 将value[u] 置为 INF
value[u] = INF;
} else if (cnt[u] == n + 1) { //第二次发现点在正环上, 直接跳过该点
continue;
}
if (u == n) {
return true;
}
for (int e = p[u]; e != -1; e = E[e].next) {
int v = E[e].v;
if (value[v] < value[u] + w[v]) {
value[v] = value[u] + w[v];
if (!vis[v]) {
vis[v] = true;
q.push(v);
cnt[v]++;
}
}
}
}
return false;
}
int main() {
int n, k, v;
init();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> k;
while (k--) {
cin >> v;
insert(i, v);
}
}
cout << (spfa(1, n) ? "Yes" : "No") << endl;
return 0;
}