| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 36860 | Accepted: 13505 |
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<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=;
const int MAXM=*;
int dis[MAXN],vis[MAXN],used[MAXN],head[MAXM];
int N,W,M,en,flot;
queue<int>dl;
struct Edge{
int from,to,value,next;
};
Edge edg[MAXM];
void initial(){
memset(dis,INF,sizeof(dis));
memset(vis,,sizeof(vis));
memset(used,,sizeof(used));
memset(head,-,sizeof(head));
while(!dl.empty())dl.pop();
en=;flot=;
}
void print(){
if(flot)puts("YES");
else puts("NO");
}
void add(int u,int v,int w){
Edge E={u,v,w,head[u]};
edg[en]=E;
head[u]=en++;
}
void SPFA(int sx){
dis[sx]=;vis[sx]=;dl.push(sx);
used[sx]++;
while(!dl.empty()){
int k=dl.front();
dl.pop();
vis[k]=;
if(used[k]>N){
flot=;
break;
}
for(int i=head[k];i!=-;i=edg[i].next){
int v=edg[i].to;
if(dis[k]+edg[i].value<dis[v]){
dis[v]=dis[k]+edg[i].value;
if(!vis[v]){
vis[v]=;
dl.push(v);
used[v]++;
if(used[v]>N){
flot=;return ;
}
}
}
}
}
}
void get(){
int F,a,b,c;
scanf("%d",&F);
while(F--){
initial();
scanf("%d%d%d",&N,&M,&W);
while(M--){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
while(W--){
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
SPFA();
print();
}
}
int main(){
get();
return ;
}
Bellman:
#include<stdio.h>
#include<string.h>
const int INF=0x3f3f3f3f;
const int MAXN=;
const int MAXM=;
int dis[MAXN];
struct Edge{
int u,v,w;
};
Edge edg[MAXM];
int N,M,W,top;
bool Bellman(int sx){
int u,v,w;
memset(dis,INF,sizeof(dis));
dis[sx]=;
for(int i=;i<=N;i++){
for(int j=;j<top;j++){
u=edg[j].u;v=edg[j].v;w=edg[j].w;
if(dis[u]+w<dis[v])dis[v]=dis[u]+w;
}
}
for(int i=;i<top;i++){
u=edg[i].u;v=edg[i].v;w=edg[i].w;
if(dis[u]+w<dis[v])return false;
}
return true;
}
int main(){
int F;
int a,b,c;
scanf("%d",&F);
while(F--){
top=;
scanf("%d%d%d",&N,&M,&W);
while(M--){
scanf("%d%d%d",&a,&b,&c);
edg[top].u=a;edg[top].v=b;edg[top++].w=c;
edg[top].u=b;edg[top].v=a;edg[top++].w=c;
}
while(W--){
scanf("%d%d%d",&a,&b,&c);
edg[top].u=a;edg[top].v=b;edg[top++].w=-c;
}
if(Bellman())puts("NO");
else puts("YES");
}
return ;
}