题目描述
John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 M条小路（无向边）连接着 N从 1到 N标号）块地，并有 W个虫洞。现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。 John 将向你提供F 个农场的地图。没有小路会耗费你超过 10^4 的时间，当然也没有虫洞回帮你回到超过 10^4秒以前。
输入
第一行一个整数F表示农场个数；对于每个农场：第一行，三个整数 N,M,W;接下来 M行，每行三个数 S,E,T 表示在标号为 S的地与标号为 E的地中间有一条用时 T秒的小路；接下来 W行，每行三个数 S,E,T 表示在标号为 S的地与标号为 E的地中间有一条可以使 John 到达 T秒前的虫洞。
输出
输出共 F行，如果 John 能在第 I个农场实现他的目标，就在第 I行输出 YES，否则输出 NO。
数据范围限制
对于全部数据:
1<=F<=5
1<=N<=500
1<=M<=2500
1<=W<=200
1<=S,E<=N
|T|<=10^4
解
迷人呐。
这道题一看其实就有思路了，因为他给我们一些富有魅力的词汇：“有向边” “有M条小路（无向边）”。于是我们不难想到最短路求解。
我一开始想要的是dijkstra，原因是被样例给迷惑了，其实他并没有说虫洞是从哪到哪，而样例都是从终点到第一个点。
我们不难看出路是双向的，而虫洞只有单向且权值为负。题目中：“现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点）”的意义就是说如果一号点到一号点的最短路为负，那么输出YES。然后刚看题意时我还很懵(´・ω・`)（不知道农场是啥），后来才发现一个农场相当于一组测试数据。
比赛交了两次，然后竟没AC——第一次visit数组（v数组，记录是否在队列中）太小，我把它开大了。然后75分，俺含着泪看了代码，链式前向星开小了（双向边×2）(┳＿┳)...。
好了，裸的负回路SPFA。
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m,w;
struct edge{
int x;//起点
int y;//终点
int val;//权值
int last;//以x为起点的上一条路在e（链式前向星）中的位置
}e[6000];
int head[2000];//head[i]表示以i为起点的最后一条路在e中的位置
int cnt;//道路数量
int dis[2000];//记录最短路
int v[2000];//是否在队列中
queue<int> q;//队列
void add(int a, int b, int v)//记录道路和虫洞（链式前向星）
{
++cnt;
e[cnt].x = a;
e[cnt].y = b;
e[cnt].val = v;
e[cnt].last = head[a];
head[a] = cnt;
}
void spfa()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(v,0,sizeof(v));
dis[1] = 0;
q.push(1);//1进队列
v[1] = 1;
while(!q.empty())
{
if(dis[1] < 0)
return;
int r = q.front();
for(int i = head[r]; i != 0; i = e[i].last)
{
int k = e[i].y;
if(dis[r] + e[i].val < dis[k])
{
dis[k] = dis[r] + e[i].val;
if(v[k] == 0)//当k不在队列中（差点忘记呀）
{
q.push(k);
v[k] = 1;
}
}
}
q.pop();
v[r] = 0;
}
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
cnt = 0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
scanf("%d%d%d", &n, &m, &w);
for(int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for(int i = 1; i <= w; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, -c);//只记录一次
}
spfa();
// for(int i = 1; i <= n; i++)//测试不用管
// printf("%d\n",dis[i]);//测试不用管 + 1
if(dis[1] < 0)
printf("YES");
else
printf("NO");
printf("\n");
}
return 0;
}