程式師世界 >> 編程語言 >> 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;
}

關於C

編程序輸出各種星號圖

/* 程序頭部注釋開始（為避免提交博文中遇到的問題，將用於表

猜測用戶的輸入星期幾

請輸入星期幾的第一個字母來判斷一下是星期幾，如果第一個字母一

問題五十七: 樓梯有n階台階，上樓可以一步上1階，也可以一步上2階，編程序計算共有多少種不同的走法？

print?/* 程序頭部注釋開始（為避免提交博文中遇到的問

Qt國際化

簡介Qt國際化屬於Qt高級中的一部分，本想著放到後面來說，上

問題三十六: 編程序輸出各種星號圖（二）

[plain]/* 程序頭部注釋開始（為避免提交博文中遇到的

I/O多路復用之select總結

1、基本概念　　IO多路復用是指內核一旦發現進程指定的一個