| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 38300 | Accepted: 14095 |
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
Hint
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int INF = ;
const int MAX = + ;
struct point
{
int e,w;
};
int F,M,N,W;
vector<point> g[MAX];
int updatetimes[MAX],dist[MAX];
/*
int spfa(int v)
{
for( int i = 1; i <= N; ++i)
dist[i] = INF;
dist[v] = 0;
queue<int> que;
que.push(v);
memset(updatetimes ,0,sizeof(updatetimes));
while( !que.empty()) {
int s = que.front();
que.pop();
for( int i = 0;i < g[s].size(); ++i) {
int e = g[s][i].e;
if( dist[e] > dist[s] + g[s][i].w ) {
dist[e] = dist[s] + g[s][i].w;
que.push(e);
++updatetimes[e];
if( updatetimes[e] >= N)
return true;
}
}
}
return false;
}
*/
int spfa(int v)
{
for(int i = ; i <= N; i++)
dist[i] = INF;
dist[v] = ;
queue<int> que;
que.push(v);
memset(updatetimes,,sizeof(updatetimes));
while(que.size())
{
int s = que.front();
que.pop();
int len = g[s].size();
for(int i = ; i < g[s].size(); i++)
{
int e = g[s][i].e;
if(dist[e] > dist[s] + g[s][i].w)
{
dist[e] = dist[s] + g[s][i].w;
que.push(e);
++updatetimes[e];
if(updatetimes[e] >= N)
return true;
}
}
}
return false;
} int main()
{
scanf("%d", &F);
while(F--)
{
scanf("%d%d%d", &N,&M,&W);
for(int i = ; i < MAX; i++)
g[i].clear();
point edge;
for(int i = ; i < M; i++)
{
int s,e,w;
scanf("%d%d%d", &s,&e,&w);
edge.e = e;
edge.w = w;
g[s].push_back(edge);
edge.e = s;
g[e].push_back(edge);
}
for(int i = ; i < W; i++)
{
int s,e,w;
scanf("%d%d%d", &s,&e,&w);
edge.e = e;
edge.w = (-) * w;
g[s].push_back(edge);
}
if(spfa())
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return ;
}
2.Ballem-ford
Bellman-Ford:算法核心就是对每个点更新一下dist[](离原点的距离)，怎么更新一个点呢，通过枚举每个边就可以了，所以每次把所有的边枚举一遍，专业术语 叫做<松弛操作>就可以确定一个点的dist，除了原点一共需要N-1个点，所以套个循环
至于判断是否存在负环呢，就在更新完所有dist,然后在枚举一下每个边，看看是否通过在增加一个边能让dist再减少，如果可以的话那就是存在负回路，因为在前面我们已经更新到最短的路径了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int INF = ;
struct Edge
{
int s,e,w;
};
vector<Edge> edge;
int dist[ + ];
int N,W,M; bool Ballem_ford(int v)
{
for(int i = ; i <= N; i++)
{
dist[i] = INF;
}
dist[v] = ;
int len = edge.size();
for(int i = ; i < N; i++)
{
for(int j = ; j < len; j++)
{
int s = edge[j].s;
int e = edge[j].e;
if(dist[e] > dist[s] + edge[j].w) //把j写成了i,真是无语
dist[e] = dist[s] + edge[j].w;
}
}
for(int i = ; i < len; i++)
{
int s = edge[i].s;
int e = edge[i].e;
if(dist[e] > dist[s] + edge[i].w)
return true;
}
return false;
}
int main()
{
int F;
scanf("%d", &F);
while(F--)
{
scanf("%d%d%d",&N,&M,&W);
edge.clear();
Edge point,temp;
for(int i = ; i < M; i++)
{
scanf("%d%d%d",&point.s,&point.e,&point.w);
edge.push_back(point);
temp.s = point.e;
temp.e = point.s;
temp.w = point.w;
edge.push_back(temp);
}
for(int i = ; i < W; i++)
{
scanf("%d%d%d", &point.s,&point.e,&point.w);
point.w = (-) * point.w;
edge.push_back(point);
}
if(Ballem_ford() == true)
printf("YES\n");
else
printf("NO\n");
}
return ;
}