在一个迷宫（图）中有一个起点和一个终点，现在你有一个最大血量maxhp，需要从起点满血出发，每条边上的权值如果是正的表示走这条边会加血，如果是负的即表示会扣血。
求抵达终点时的最大血量，如果中途血小于等于0即为game over。
最简单的想法是使用Extended Bellman-Ford，对所有点进行松弛，在可以回血的环上不停更新各个节点直到没有可以更新的节点。
这样复杂度为O(n*m*maxhp) 明显不行
注意到主要浪费的时间在这种治疗环上，所以需要尽快跳过治疗环。这里只需要对每个点都往后找n-1步，如果有环必然可以发现，然后O(n)将至少一个节点变为maxhp
由于对每个节点都只找了一次环，所以就可以不管maxhp的复杂度，将复杂度限制在了O(n^2*m)。
虽然如此，这个做法效率并不高，有空还会考虑一下其他解法
/*author: birdstorm*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <climits>#define MAXN 1005
#define N 105
#define inf 1.0e20
#define eps 1.0e-8
#define MOD 1000000007#define For(i,m,n) for(int i=(m);i<(n);i++)
#define vecfor(iter,a) for(vector<int>::iterator iter=a.begin();iter!=a.end();iter++)
#define rep(i,m,n) for(int i=(m);i<=(n);i++)
#define repd(i,m,n) for(int i=(m);i>=(n);i--)
#define LL long long
#define testusing namespace std;int loop[MAXN], cost[MAXN], t[MAXN];
struct Edge{int y, cost;Edge(){}Edge(int y, int cost): y(y), cost(cost) {}
};
vector<Edge> g[MAXN];int relax(int n, int st, int maxhp)
{memset(t,0,sizeof t);int sz=g[st].size();For(i,0,sz){int idx=g[st][i].y;t[idx]=min(maxhp,max(t[idx],maxhp+g[st][i].cost));}For(i,0,n-1) For(j,0,n){if(!t[j]) continue;int sz=g[j].size();For(k,0,sz){int idx=g[j][k].y;t[idx]=min(maxhp,max(t[idx],t[j]+g[j][k].cost));}}return t[st];
}int calc(int n, int s, int d, int maxhp)
{int x;memset(cost,0,sizeof cost);For(i,0,n){if(maxhp==relax(n,i,maxhp))loop[i]=1;else loop[i]=0;}cost[s]=maxhp;For(i,0,n){For(j,0,n){if(!cost[j]) continue;int sz=g[j].size();For(k,0,sz){int idx=g[j][k].y;cost[idx]=min(maxhp,max(cost[idx],cost[j]+g[j][k].cost));}}For(j,0,n){if(!cost[j]) continue;int sz=g[j].size();For(k,0,sz){int idx=g[j][k].y;if(cost[idx]!=min(maxhp,cost[j])&&loop[idx]) cost[idx]=maxhp;}}}return cost[d];
}int main()
{int n, m;int cs=1;int st, di, hp;int x,y,cst;while(scanf("%d%d",&n,&m),n||m){For(i,0,n) g[i].clear();memset(loop,0,sizeof loop);For(i,0,m){scanf("%d%d%d",&x,&y,&cst);g[x].push_back(Edge(y,cst));}scanf("%d%d%d",&st,&di,&hp);g[di].clear();printf("Case %d: ",cs++);int ans=calc(n,st,di,hp);if(ans<=0) printf("GAME OVER\n");else printf("%d\n",ans);}return 0;
}