| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 35235 | Accepted: 12861 |
Description
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 ≤ N ≤ 500) 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 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
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+前向星 算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#define exp 1e-9
#define INF 0x3f3f3f3f
using namespace std;
const int Max=550;
struct node
{
int v;
int w;
int next;
} Map[Max],Head[10000];
int Dis[Max];
bool vis[Max];
int path[Max];
int Du[Max];
int n,m,w;
int top;
bool SPFA(int star)
{
queue<int >Q;
memset(Dis,INF,sizeof(Dis));
memset(vis,false,sizeof(vis));
memset(Du,0,sizeof(Du));
memset(path,1,sizeof(path));
Q.push(star);
vis[star]=true;
Du[star]++;
Dis[star]=0;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(Du[u]>n)
return true;
vis[u]=false;
int p=Map[u].next;
while(p!=-1)
{
if(Dis[Head[p].v]>Dis[u]+Head[p].w)
{
Dis[Head[p].v]=Dis[u]+Head[p].w;
if(!vis[Head[p].v])
{
Q.push(Head[p].v);
Du[Head[p].v]++;
vis[Head[p].v]=true;
}
}
p=Head[p].next;
}
}
return false;
}
void Creat(int u,int v,int ww)
{
Head[top].next=Map[u].next;
Map[u].next=top;
Head[top].v=v;
Head[top].w=ww;
top++;
}
int main()
{
int T;
int u,v,ww;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&n,&m,&w);
top=0;
for(int i=0; i<=n; i++)
{
Map[i].next=-1;
}
for(int i=0; i<m; i++)
{
scanf("%d %d %d",&u,&v,&ww);
Creat(u,v,ww);
Creat(v,u,ww);
}
for(int i=0; i<w; i++)
{
scanf("%d %d %d",&u,&v,&ww);
Creat(u,v,-ww);
}
if(SPFA(1))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。