洛谷 P2850 [USACO06DEC]虫洞Wormholes
题目描述 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.
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
输入输出格式
输入格式：
Line 1: A single integer, F. F farm descriptions follow.
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.
输出格式：
Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
输入输出样例 输入样例#1：
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
输出样例#1：
NO YES
说明 For farm 1, FJ cannot travel back in time.
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.
题目的大意应该已经很清楚了。
不过在此之前我也没做过负环的题，然后就按着最短路的思路写了一下。
【洛谷 P2850 [USACO06DEC]虫洞Wormholes】最初我是直接跑一遍BFS版的SPFA，然后记录下遍历过的点。
如果某个点遍历过2次，那么就有环，否则无环。
然后一遍过了样例就直接交上去了。然后不加优化果然是T了的。
然后某位dalao告诉我负环可以用DFS版的SPFA。
其实两个版本的SPFA都差不多。
思路和注释差不多都在代码里了
#include
#include
#include
#include
using namespace std;
const int MAXN=10001;
int k,n,m,w,tot=0;
int Head[MAXN],Dis[MAXN];
//Head表示邻接表的头点，Dis[i]表示从起始点到i点的当前距离。
bool visit[MAXN],flag=0;
//visit记录是否遍历到了这个点。
struct edge//邻接表存图
{
int next,node,w;
}h[MAXN*4];
void add(int u,int v,int w)//加点
{
h[++tot].next=Head[u];
h[tot].node=v;
h[tot].w=w;
Head[u]=tot;
//虽然有重边但是不用去判断了。
}
void SPFA(int x)
{
if(flag)
return ;
visit[x]=1;
//记录下所有遍历的点
for(int i=Head[x];
i;
i=h[i].next)//和跑最短路基本一样
{
if(flag)
return ;
int v=h[i].node;
if(Dis[v]>Dis[x]+h[i].w)
{
Dis[v]=Dis[x]+h[i].w;
if(visit[v])//如果已经遍历过了就直接跳出去了。
{
flag=1;
return ;
}
else
SPFA(v);
//继续遍历
}
}
visit[x]=0;
//回溯的时候将遍历过的点还原
}
int main()
{
cin>>k;
while(k--)
{
tot=0;
//每个数据要记得清0,
flag=0;
memset(h,0,sizeof(h));
memset(visit,0,sizeof(visit));
memset(Head,0,sizeof(Head));
memset(Dis,0,sizeof(Dis));
//这里需要注意一下，Dis初始设置成0能跳过很多路径，
cin>>n>>m>>w;
//直接找到负数点所在的环。
for(int i=1;
i<=m;
i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
//正权边是双向的需要注意一下。
}
for(int i=1;
i<=w;
i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,-z);
//这道题很方便的就是负权边都放一起了不用去打判断。
}
for(int i=1;
i<=n;
i++) //其实吧，这里随便找个点SPFA都行，毕竟有负环从哪个点开始都能找到，
{//而且只要跑一遍就行了。
if(flag)
break;
//发现负环直接退出循环。
SPFA(i);
}
if(flag)
cout<<"YES"< 推荐阅读
- 洛谷 P5056 【模板】插头dp
- C++|【暖*墟】 #洛谷省选网课# 8.1数论进阶
- 洛谷|洛谷 P1481 魔族密码
- SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)
- KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）
- JSOI2018冬令营游记&总结（迁移自洛谷博客）
- 洛谷P5471 NOI2019弹跳
- 【洛谷P4144】大河的序列
- C++|高精度加法 洛谷 P1601 A+B Problem（高精）
- BZOJ5157|BZOJ5157 & 洛谷3970（[TJOI2014]上升子序列——题解）