程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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();
    }
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved