虫の穴

Problem 3虫洞(wormhole.cpp/c/pas)
【タイトル説明】
ジョンは彼の農場をぶらぶらしている間にたくさんの虫の穴を見つけた.虫の穴は非常に奇妙な縁と見なすことができます過去の時刻(虫の穴に入る前に)に戻ることができます.ジョンの農場ごとにM本の小道(無方向の辺)がN(1..N記号から)ブロックに接続され、W個の虫の穴(方向の辺)があります.そのうち1<=N<=500、1<=M<=2500、1<=W<=200です.今、ジョンはこれらの虫の穴を助けて過去に戻りたいと思っています.(出発時刻までに)、できるか教えてください.ジョンはF(1<=F<=5)農場の地図を提供します.小道がないと10000秒を超える時間がかかります.もちろん、虫の穴が10000秒を超える前に戻ってくることもありません.
【入力形式】
*Line 1:農場数を表す整数F.
*Line 1 of each farm:3つの整数N,M,W.
* Lines 2..M+1 of each farm:3つの数(S,E,T).Sと表記された地とEと表記された地の間にT秒の小道があることを示す.
* Lines M+2..M+W+1 of each farm:3つの数(S,E,T).Sと表記された地とEと表記された地の間にJohnをT秒前に到達させることができる虫穴があることを示す.
【出力形式】
* Lines 1..F:ジョンがこの農場で目標を達成できれば、「YES」を出力し、そうでなければ「NO」を出力します.
【サンプル入力】
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
【サンプル出力】
NO
YES
【問題解】
負の重みの有無を判断する回路
この問題のデータは意外にも普通のspfaです.
dfs版のspfaで
【コード】

#include 
#include 
#include 
#define ll long long
#define inf 5000010
#define maxn 600
#define maxm 6000 
using namespace std;
ll head[maxn], next[maxm], to[maxm], w[maxm], dist[maxm], n, m, F, tot, vis[maxn];
void add(ll a, ll b, ll v){to[++tot]=b;w[tot]=v;next[tot]=head[a];head[a]=tot;}
void init()
{
	ll i, j, a, b, v, c, *p;
	memset(head,0,sizeof(head));
	memset(vis,0,sizeof(vis));
	memset(dist,0x3f,sizeof(dist));
	tot=0;
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for(i=1;i<=m;i++)scanf("%I64d%I64d%I64d",&a,&b,&v),add(a,b,v),add(b,a,v);
	for(i=1;i<=c;i++)scanf("%I64d%I64d%I64d",&a,&b,&v),add(a,b,-v);
}
bool spfa(ll pos)
{
	ll p;
	vis[pos]=true;
	for(p=head[pos];p;p=next[p])
	{
		if(dist[to[p]]>dist[pos]+w[p])
		{
			dist[to[p]]=dist[pos]+w[p];
			if(vis[to[p]])return true;
			if(spfa(to[p]))return true;
		}
	}
	vis[pos]=false;
	return false;
}
int main()
{
	freopen("wormhole.in","r",stdin);
	freopen("wormhole.out","w",stdout);
	scanf("%I64d",&F);
	while(F--)
	{
		init();
		dist[1]=0;
		printf(spfa(1)?"YES
":"NO
");
	}
	return 0;
}