程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1317 XYZZY

HDU 1317 XYZZY

編輯：C++入門知識

題意是指從1 到 N 能否保證到達每個點的時候能量都為正數。

起點 1 初始100 點能量。

輸入是從 1 ~ N ，分別是能量，能到m個房間，分別是 a1,a2,a3,…,am

可以給每個能到達的點而產生的邊賦權，即能量值。

SPFA 求最長路的變形，出現負環不怕，出現正環就需要一點改動。

vis[]標記是否需要入隊，d[] 表示能量，que[] 表示入隊次數。

如果出現正環（que[v]>=n），表明一定能保證到達每個點的時候都是正能量。

這時候直接將 d[v] 賦最大值（因為可以一直循環獲得正能量），並下一次的時候不再入隊。

最後 d[n]>0 表明能行。

//C++ 0ms
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0xfffffff
#define eps 1e-6
using namespace std;
int n,m;
struct lx
{
    int v,en;
};
vector g[101];

int d[101];
bool vis[101];
int que[101];
void SPFA()
{
    for(int i=1; i<=n; i++)
        d[i]=-INF,vis[i]=0,que[i]=0;
    queueq;
    d[1]=100,vis[1]=1,que[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        if(que[u]>n)continue;// >=  WA
        for(int j=0; j0)
            {
                d[v]=d[u]+en;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                    if(++que[v]>=n)d[v]=INF;
                }
            }
        }
    }
    if(d[n]>0)puts("winnable");
    else puts("hopeless");
}
int main()
{
    while(scanf("%d",&n),n!=-1)
    {
        int en,v,u;
        for(int i=0; i<=n; i++)
            g[i].clear();
        for(int i=1; i<=n; i++)
        {
            u=i;
            scanf("%d%d",&en,&m);
            lx now;
            now.en=en;
            while(m--)
            {
                scanf("%d",&v);
                now.v=v;
                g[u].push_back(now);
            }
        }
        SPFA();
    }
}