程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> hdu3592 World Exhibition --- 差分約束

hdu3592 World Exhibition --- 差分約束

編輯：關於C語言

hdu3592 World Exhibition --- 差分約束

這題建圖沒什麼特別

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;
}