https://vjudge.net/contest/66569#problem/F
题意：判断图中是否存在负权回路
首先，介绍图的邻接表存储方式
邻接表建图，类似于头插法建单链表
head[x]：以x为源点的第一条边，初始值为-1.
struct edge
{
int to;
int weight;
int next;
}e[maxn];
to表示被指向的点；weight表示这条边的权重；next表示源点同为x的下一条边,这是遍历以x为源点的的关键
SPFA算法中的队列与BFS不同的是，每个点都可以在重复进入队列，而且进入队列总次数大于顶点总数说明该图存在负环。这是因为每个点的估计最短路可能在出队列后被更新，这样这个点就可以再次进入队列去更新其他点。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
const int inf=0x3f3f3f3f;
int n,m,w;
struct edge
{
int to;
int time;
int next;
}e[maxn];
int head[]; int Spfa(int src)
{
//记录每个顶点到src的距离，除了src,其余点都初始化为无穷大
int dis[];
memset(dis,inf,sizeof(dis));
dis[src]=;
//记录每个顶点进入队列的总次数，大于n说明有负环
int cnt[];
memset(cnt,,sizeof(cnt));
//记录是否在队列中
bool inque[];
memset(inque,,sizeof(inque));
queue<int> Q;
//源点进如队列
Q.push(src);
inque[src]=;
cnt[src]++;
while(!Q.empty())
{
int q=Q.front();
Q.pop();
//记录已经出队列
inque[q]=;
//邻接表，i表示边
for(int i=head[q];i!=-;i=e[i].next)
{
//对每个点进行松弛，逐渐逼近最小值
if(dis[q]+e[i].time<dis[e[i].to])
{
dis[e[i].to]=dis[q]+e[i].time;
//如果更新成功而且当前不在队列中，进入队列且总次数加1
if(!inque[e[i].to])
{
inque[e[i].to]=;
cnt[e[i].to]++;
Q.push(e[i].to);
//说明存在负环
if(cnt[e[i].to]>n)
{
return ;
}
}
}
}
}
return ;
}
int main()
{
int T;
scanf("%d",&T);
int x,y,t;
while(T--)
{
memset(head,-,sizeof(head));
scanf("%d%d%d",&n,&m,&w);
int tot=;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&t);
e[tot].to=y;
e[tot].time=t;
e[tot].next=head[x];
head[x]=tot++;
e[tot].to=x;
e[tot].time=t;
e[tot].next=head[y];
head[y]=tot++;
}
for(int i=;i<=w;i++)
{
scanf("%d%d%d",&x,&y,&t);
e[tot].to=y;
e[tot].time=-t;
e[tot].next=head[x];
head[x]=tot++;
}
int ans=Spfa();
if(ans==)
{
puts("YES");
}
else
{
puts("NO");
}
}
return ;
}
邻接表+SPFA
理论上以任意一点为源点都是可以的，顶点的数据范围是1~N，所以Spfa(1)或Spfa(n)都可以AC，其他的具体值不可以