hdu 1317 XYZZY(spfa判环) - c++编程基础

http://acm.hdu.edu.cn/showproblem.php pid=1317

大致题意：有n个房间，每个房间都有对应的能量值（可正可负），现在从1出发要到达n，初始能量为100，问是否能够达到n点，到达n的条件是中间及最后的能量值都要大于0.

思路：若不考虑环，那么求最长路判断是否大于0即可。若存在负环，对求最长路也没影响；但当存在正环时，最长路就不存在了。可用spfa判断，当某点入队超过n次，那么它必定在环中，直接将其dis置为INF，并不再将其近队列。最后若能到达n则可行，否则失败。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 110; int n; int dis[maxn]; int inque[maxn]; int out[maxn]; vector 
            
              edge[maxn]; int w[maxn]; bool spfa() { queue 
             
               que; memset(dis,-INF,sizeof(dis)); memset(inque,0,sizeof(inque)); memset(out,0,sizeof(out)); inque[1] = 1; dis[1] = 100; que.push(1); while(!que.empty()) { int u = que.front(); que.pop(); inque[u] = 0; out[u]++; if(out[u] > n) //在环中不再仅队列 continue; if(out[u] == n) //将dis置为INF dis[u] = INF; for(int i = 0; i < (int)edge[u].size(); i++) { int v = edge[u][i]; if(dis[v] < dis[u] + w[v] && dis[u] + w[v] > 0)//注意中间也要保证>0 { dis[v] = dis[u] + w[v]; if(v == n) //能够到达n返回true return true; if(!inque[v]) { inque[v] = 1; que.push(v); } } } } return false; } int main() { int num,v; while(~scanf("%d",&n)) { if(n == -1) break; for(int i = 1; i <= n; i++) { edge[i].clear(); scanf("%d",&w[i]); scanf("%d",&num); while(num--) { scanf("%d",&v); edge[i].push_back(v); } } if(spfa()) printf("winnable\n"); else printf("hopeless\n"); } return 0; }