程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3259 Wormholes(spfa)

poj 3259 Wormholes(spfa)

編輯:C++入門知識

poj 3259 Wormholes(spfa)


#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1024;

struct node
{
    int to;
    int w;
    node *next;
};

node* edge[N];
int n,m,w,cnt[N],vis[N],dist[N];
queueq;

int spfa(int v0)
{
    while(!q.empty()) q.pop();
    int i,u;
    node *ptr;
    for(i=1; in) return 1;
        ptr=edge[u];
        while(ptr!=NULL)
        {
            if(dist[ptr->to]>dist[u]+ptr->w)
            {
                dist[ptr->to]=dist[u]+ptr->w;
                if(vis[ptr->to]==0)
                {
                    vis[ptr->to]=1;
                    cnt[ptr->to]++;
                    q.push(ptr->to);
                }
            }
            ptr=ptr->next;
        }
    }
    return 0;
}

int main()
{
    int _,i,u,v,t,flag;
    node* temp;
    scanf("%d",&_);
    while(_--)
    {
        scanf("%d%d%d",&n,&m,&w);
        for(i=1; ito=v;
            temp->w=t;
            temp->next=NULL;
            if(edge[u]==NULL)
            {
                edge[u]=temp;
            }
            else
            {
                temp->next=edge[u];
                edge[u]=temp;
            }

            temp=new node;
            temp->to=u;
            temp->w=t;
            temp->next=NULL;
            if(edge[v]==NULL)
            {
                edge[v]=temp;
            }
            else
            {
                temp->next=edge[v];
                edge[v]=temp;
            }

        }
        for(i=0; ito=v;
            temp->w=-t;
            temp->next=NULL;
            if(edge[u]==NULL)
            {
                edge[u]=temp;
            }
            else
            {
                temp->next=edge[u];
                edge[u]=temp;
            }
        }
        flag=spfa(1);
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

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