poj3259-Wormholes

題目傳送:poj3259
注意:本題起點為1,spfa做法:一共n個節(jié)點陨界,每個節(jié)點進入隊列的次數(shù)至多為n-1次栏赴,若進入大于等于n次盈咳,說明圖中存在負(fù)權(quán)回路耿眉,滿足“and return to the starting field a time before his initial departure”的條件,田里道路雙向鱼响,蟲洞單向且為負(fù)邊鸣剪。

題目描述:
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N
(1\leN\le500)fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2.. M+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2.. M+ W+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output
Lines 1.. F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output
NO
YES

Hint
For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

SPFA:

//#include<bits/stdc++.h>
#include<cstring>
#include<cstdio>
#include<queue>
//#include<iostream>
using namespace std;
const int maxn=1e4;
const int inf=1e9;
int e[maxn][maxn];
//int dis[maxn];
bool spfa(int start,int N){
    int book[maxn],sum[maxn],dis[maxn];
    memset(book,0,sizeof(book));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=N;i++)
        dis[i]=inf;
    dis[start]=0;
    queue<int>q;
    //q.clear();//C++中的queue自身不支持clear操作,雙端隊列deque支持clear操作
    while(!q.empty())q.pop();
    q.push(start);
    book[start]=1;//注意不是book[1]=1;
    ++sum[start];
    while(!q.empty()){
        int x=q.front();
        q.pop();
        book[x]=0;
        for(int i=1;i<=N;i++){
            //if(sum[i]>N)return true;
            if(e[x][i]<inf&&dis[i]>dis[x]+e[x][i]){//e[x][i]<inf條件不要忘記加丈积,用鄰接矩陣存圖時筐骇,有邊才能松弛
                dis[i]=dis[x]+e[x][i];
                if(!book[i]){
                    book[i]=1;
                    q.push(i);
                    ++sum[i];
                    if(sum[i]>=N)return true;//是否加=?
                }
            }
        }
    }
    return false;
}
int main(){
    int F,N,M,W,S,E,T;
    int st;
    scanf("%d",&F);
    for(int k=1;k<=F;k++){
        scanf("%d%d%d",&N,&M,&W);
        for(int i=1;i<=N;i++){//二維e數(shù)組初始化
            for(int j=1;j<=N;j++){
                if(i==j)e[i][j]=0;
                else e[i][j]=inf;
            }
        }
        for(int i=1;i<=M;i++){//田地里的路桶癣,無說明,注意雙向娘锁,讀入正邊
            scanf("%d%d%d",&S,&E,&T);//有重復(fù)邊牙寞?暫假設(shè)沒有
            if(e[S][E]>T)
                e[S][E]=e[E][S]=T;
            if(i==1)st=S;
        }
        for(int i=1;i<=W;i++){//讀入負(fù)邊
            scanf("%d%d%d",&S,&E,&T);
            e[S][E]=-T;
            //e[S][E]=e[E][S]=-T;//蟲洞的負(fù)邊是單向的
        }
        //cout<<M<<endl;
        if(spfa(st,N))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
    

做完這道題有幾點醒悟:一開始時候總是糾結(jié)于題目沒說明起點,該定哪個點為起點呢莫秆,上面的代碼想了一天從wa到ac,后來終于發(fā)現(xiàn)由于習(xí)慣性思維把1當(dāng)做起點间雀,把book[start]=1;寫成了book[1]=1; 不過也正是這個錯誤讓我突然明白這道題和起點是哪個點一點關(guān)系也沒有,只要圖是聯(lián)通的镊屎,可以設(shè)置任何點為起點惹挟,計算其他點到這個規(guī)定的起點的距離來判斷這個圖是否存在負(fù)環(huán)。而我則很蠢的把第一個輸入的點作為起點來松弛缝驳。所以就一句話连锯,判斷有沒有負(fù)環(huán)就完事了归苍,如果圖是聯(lián)通的管他誰是起點。

vector寫法:
spfa:

#include<iostream>
#include<vector>
#include<queue>
const int INF=1e9;
const int maxn=1e3+10;
using namespace std;
struct edge{
    int v;
    int w;
}edges[maxn*10];
vector<edge>v[maxn];//v可以看出一個二維數(shù)組
bool book[maxn];
int dis[maxn];
int sum[maxn];
int n,m,w,cnt;
void readedge(int e,int s,int t){//讀入邊
    cnt++;
    edges[cnt].v=s;
    edges[cnt].w=t;
    v[e].push_back(edges[cnt]);//v數(shù)組下標(biāo)是起點运怖,該數(shù)組記錄了每個起點的所有邊拼弃,v[e].size()就是以e為起點的所有出邊的數(shù)量
}
bool spfa(){
    queue<int>q;
    book[1]=1;
    dis[1]=0;
    sum[1]=1;
    for(int i=2;i<=n;i++){
        book[i]=0;
        dis[i]=INF;
        sum[i]=0;
    }
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        book[x]=0;
        for(int i=0;i<v[x].size();i++){
            if(dis[v[x][i].v]>dis[x]+v[x][i].w){
                dis[v[x][i].v]=dis[x]+v[x][i].w;
                if(!book[v[x][i].v]){                   
                    book[v[x][i].v]=1;
                    sum[v[x][i].v]++;
                    if(sum[v[x][i].v]>=n)//某點入隊的次數(shù)大于等于n,該圖必然存在負(fù)環(huán)
                        return true;
                    q.push(v[x][i].v);//把能松弛且不在隊列的點入隊
                }
            }
        }
    }
    return false;
}
int main(){
    int f;
    cin>>f;
    for(int k=1;k<=f;k++){
        cin>>n>>m>>w;
        cnt=0;
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=0;i<m;i++){//讀入邊
            int s,e,t;
            cin>>s>>e>>t;
            readedge(s,e,t);
            readedge(e,s,t);//道路為雙向摇展,所以要反向讀入一次
        }
        for(int i=0;i<w;i++){
            int s,e,t;
            cin>>s>>e>>t;
            readedge(s,e,-t);//蟲洞數(shù)據(jù)是單向的負(fù)邊
        }
        if(spfa())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末吻氧,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子咏连,更是在濱河造成了極大的恐慌盯孙,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件祟滴,死亡現(xiàn)場離奇詭異振惰,居然都是意外死亡,警方通過查閱死者的電腦和手機踱启,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門报账,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人埠偿,你說我怎么就攤上這事透罢。” “怎么了冠蒋?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵羽圃,是天一觀的道長。 經(jīng)常有香客問我抖剿,道長朽寞,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任斩郎,我火速辦了婚禮脑融,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘缩宜。我一直安慰自己肘迎,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布锻煌。 她就那樣靜靜地躺著妓布,像睡著了一般。 火紅的嫁衣襯著肌膚如雪宋梧。 梳的紋絲不亂的頭發(fā)上匣沼,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機與錄音捂龄,去河邊找鬼释涛。 笑死加叁,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的枢贿。 我是一名探鬼主播殉农,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼局荚!你這毒婦竟也來了超凳?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤耀态,失蹤者是張志新(化名)和其女友劉穎轮傍,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體首装,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡创夜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了仙逻。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片驰吓。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖系奉,靈堂內(nèi)的尸體忽然破棺而出檬贰,到底是詐尸還是另有隱情,我是刑警寧澤缺亮,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布翁涤,位于F島的核電站,受9級特大地震影響萌踱,放射性物質(zhì)發(fā)生泄漏葵礼。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一并鸵、第九天 我趴在偏房一處隱蔽的房頂上張望鸳粉。 院中可真熱鬧,春花似錦园担、人聲如沸届谈。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽疼约。三九已至卤档,卻和暖如春蝙泼,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背劝枣。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工汤踏, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留织鲸,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓溪胶,卻偏偏與公主長得像搂擦,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子哗脖,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,350評論 0 10
  • The Inner Game of Tennis W Timothy Gallwey Jonathan Cape ...
    網(wǎng)事_79a3閱讀 12,107評論 3 20
  • 長長的鐵軌瀑踢,嗚嗚的轟鳴聲,火車總是在眼前呼嘯而過才避,沒有片刻的停留橱夭,最美的是沿途的風(fēng)景,最好的是火車上的偶遇桑逝。 狹小...
    玄白不白閱讀 353評論 0 1
  • 你胸口的痣 是遠(yuǎn)方的一座孤島 而我順著孤單的方向 渴望你一望無際的海
    每日一濕閱讀 249評論 0 0
  • 【月回顧模板】 一棘劣、一月整體分析 (主要分析說明一月份的三個核心目標(biāo)的完成情況) 二、各領(lǐng)域情況分析 (主要分析自...
    盛某閱讀 187評論 0 0