程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> hdu3592 World Exhibition

hdu3592 World Exhibition

編輯:關於C

這題建圖沒什麼特別

x個條件:Sb-Sa<=c

y個條件:Sa-Sb<=-c

題目問的是,1和n之間的關系。

有負環的話,整個就不可能成立,輸出-1

如果圖是連通的(1到n是連通的),就輸出d[n]

不連通就是題目中說-2的情況。


原來我們建圖一般添加一個附加結點,或者開始就把所有點入隊,就是考慮到不連通的問題,所以添加一個沒有意義的條件。


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll __int64
using namespace std;
#define N 1010

struct node
{
    int v,w,next;
}e[30020];
int d[N],inq[N],outq[N],n,head[N],h;

void addedge(int a,int b,int c)
{
    e[h].v=b;
    e[h].w=c;
    e[h].next=head[a];
    head[a]=h++;
}

int spfa(int s)
{
    memset(d,0x3f,sizeof d);
    memset(inq,0,sizeof inq);
    memset(outq,0,sizeof outq);
    d[s]=0;inq[s]=1;
    queue q;
    q.push(s);
    int i,x;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        inq[x]=0;
        outq[x]++;
        if(outq[x]>n) return 0;
        for(i=head[x];i!=-1;i=e[i].next)
        {
            if(d[e[i].v]>d[x]+e[i].w)
            {
                d[e[i].v]=d[x]+e[i].w;
                if(!inq[e[i].v])
                {
                    inq[e[i].v]=1;
                    q.push(e[i].v);
                }
            }
        }
    }
    return 1;
}

void init()
{
    memset(head,-1,sizeof head);
    h=0;
}

int main()
{
    int T,a,b,c,x,y;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d%d",&n,&x,&y);
        while(x--)
        {
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
        }
        while(y--)
        {
            scanf("%d%d%d",&a,&b,&c);
            addedge(b,a,-c);
        }
        if(!spfa(1))
            printf("-1\n");
        else if(d[n]!=inf)
            printf("%d\n",d[n]);
        else printf("-2\n");
    }
    return 0;
}


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