题意：
有n个点 m条边 每个边有权值
一开始有一百血 每次经过一条路都会加上其权值
判断是否能够到达n
显然 有正环的时候肯定能够到达
最短路好题!!!!!!!
显用folyed判断是否联通
然后用spfa更新最长路
因为每次更新的都是最长路 所有有环的时候肯定是正环 这时候直接return即可
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f #define N 300 struct node { int v,to,nex; }edge[1000000]; int head[N],pos=0; void add(int a,int b,int c) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].v=c; edge[pos].to=b; } int mp[N][N]; int n; int vis[N]; int dis[N]; int cnt[N]; bool spfa() { rep(i,1,n) { vis[i]=0; dis[i]=-inf;//求最长路 cnt[i]=0; } queue<int>q; q.push(1); vis[1]=1; cnt[1]=1; dis[1]=100; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=head[u];i;i=edge[i].nex) { int v=edge[i].to; if(dis[v]<dis[u]+edge[i].v && dis[u]+edge[i].v>0 ) { dis[v]=dis[u]+edge[i].v; if(!vis[v]) { cnt[v]++; if(cnt[v]>n)return mp[v][n];//这里写成mp[i][n]dubug了一个小时 vis[v]=1; q.push(v); } } } } return dis[n]>0; } int main() { while(RI(n)&&n!=-1) { rep(i,1,n)rep(j,1,n)if(i!=j)mp[i][j]=0;else mp[i][j]=1; pos=0; CLR(head,0); rep(i,1,n) { int v,k;RII(v,k); while(k--) { int x; RI(x); mp[i][x]=1; add(i,x,v); } } rep(k,1,n) rep(i,1,n) rep(j,1,n) mp[i][j]=mp[i][j]||mp[i][k]&&mp[k][j]; if(!mp[1][n]) printf("hopeless "); else { if(spfa()) printf("winnable "); else printf("hopeless "); } } return 0; }