Description

John在他的農(nóng)場中閑逛時發(fā)現(xiàn)了許多蟲洞。蟲洞可以看作一條十分奇特的有向邊，并可以使你返回到過去的一個時刻（相對你進入蟲洞之前）。John的每個農(nóng)場有M條小路（無向邊)連接著N （從1..N標(biāo)號）塊地，并有W個蟲洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 現(xiàn)在John想借助這些蟲洞來回到過去（出發(fā)時刻之前），請你告訴他能辦到嗎。 John將向你提供F(1<=F<=5)個農(nóng)場的地圖。沒有小路會耗費你超過10000秒的時間，當(dāng)然也沒有蟲洞回幫你回到超過10000秒以前。

Input

* Line 1: 一個整數(shù) F, 表示農(nóng)場個數(shù)。

* Line 1 of each farm: 三個整數(shù) N, M, W。

* Lines 2..M+1 of each farm: 三個數(shù)（S, E, T）。表示在標(biāo)號為S的地與標(biāo)號為E的地中間有一條用時T秒的小路。

* Lines M+2..M+W+1 of each farm: 三個數(shù)（S, E, T）。表示在標(biāo)號為S的地與標(biāo)號為E的地中間有一條可以使John到達T秒前的蟲洞。

Output

* Lines 1..F: 如果John能在這個農(nóng)場實現(xiàn)他的目標(biāo)，輸出"YES",否則輸出"NO"。

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

spfa判負環(huán)……還寫的是dfs的spfa……大概會快一點

真是斯巴達……加邊的時候前m條要加雙向邊，后w條只加單向邊……因此不明不白的wa了好幾次

#include<cstdio> #include<cstring> int n,m,w,cnt,len,head[10001],dist[10001]; bool flag[10001],ans; int s[10001]; struct edge{int to,next,v; }e[100001]; inline void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt; } inline void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w); } inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline void spfa(int x) {flag[x]=1;for (int i=head[x];i;i=e[i].next){if (dist[x]+e[i].v<dist[e[i].to]){if (flag[e[i].to]) {ans=1;return;}dist[e[i].to]=dist[x]+e[i].v;spfa(e[i].to);}}flag[x]=0; } inline bool judge() {ans=0;for (int i=1;i<=n;i++){memset(flag,0,sizeof(flag));memset(dist,0,sizeof(dist));spfa(i);if (ans) return 1;}return 0; } inline bool work() {memset(e,0,sizeof(e));memset(head,0,sizeof(head));cnt=0;n=read();m=read();w=read();for (int i=1;i<=m;i++){int x=read(),y=read(),z=read();insert(x,y,z);}for (int i=1;i<=w;i++){int x=read(),y=read(),z=read();ins(x,y,-z);}if (judge()) return 1;else return 0; } int T; int main() {T=read();while (T--)s[++len]=work();for (int i=1;i<=len;i++)if (s[i]) printf("YES\n");else printf("NO\n"); }

轉(zhuǎn)載于:https://www.cnblogs.com/zhber/p/4035971.html

總結(jié)

以上是生活随笔為你收集整理的bzoj1715[Usaco2006 Dec]Wormholes 虫洞的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。