题目大意:
农民约翰在农场散步的时候发现农场有大量的虫洞,这些虫洞是非常特别的因为它们都是单向通道,为了方便现在把约翰的农田划分成N快区域,M条道路,W的虫洞。
约翰是时空旅行的粉丝,他希望这样做,在一个区域开始,经过一些道路和虫洞然后回到他原来所在的位置,这样也许他就能见到他自己了。
穿越虫洞会回到以前。。。。。(穿越者约翰)
/////////////////////////////////////////////////////////////
很明显这是一个很扯淡的故事,不过为了出一道带负权值的题目也是难为了出题人,迪杰斯特拉算法不能处理带有负权值的问题,佛洛依德倒是可以,不过复杂度很明显太高,所以spfa是不错的选择,只需要判断出发点时间是否变小.
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std; const int maxn = ;
const int oo = 0xfffffff; struct node
{
int y, time;
node(int y, int t):y(y), time(t){}
};
vector<node> G[maxn];
int v[maxn]; int spfa(int s)
{
queue<int> Q;
Q.push(s); while(Q.size())
{
s = Q.front();Q.pop();
int len = G[s].size(); for(int i=; i<len; i++)
{
node q = G[s][i]; if(v[s]+q.time < v[q.y])
{
v[q.y] = v[s] + q.time;
Q.push(q.y);
}
} if(v[] < )
return ;
} return ;
} int main()
{
int T; scanf("%d", &T); while(T--)
{
int N, M, W, i, a, b, c; scanf("%d%d%d", &N, &M, &W); for(i=; i<=N; i++)
{
v[i] = oo;
G[i].clear();
}
v[] = ; for(i=; i<M; i++)
{
scanf("%d%d%d", &a, &b, &c);
G[a].push_back(node(b, c));
G[b].push_back(node(a, c));
} for(i=; i<W; i++)
{
scanf("%d%d%d", &a, &b, &c);
G[a].push_back(node(b, -c));
} int ans = spfa(); if(ans == )
printf("YES\n");
else
printf("NO\n");
} return ;
}