题意：给出点到点的距离，和一些虫洞（即负距离），求解是否能形成负环
思路：bellman_ford算法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define Max 2005
#define inf 1<<28
using namespace std;
int N,M,W;
int dis[Max];
bool visit[Max];
struct kdq
{
int s,e,l;
} line[Max*10];
int edge;
int bellman_ford(int s)
{
int i,j;
for(i=0; i<N; i++)
dis[i]=inf;
dis[s]=0;
int flag=0;
for(i=0; i<N-1; i++)
{
for(j=0; j<edge; j++)
{
if(dis[line[j].s]!=inf&&dis[line[j].s]+line[j].l<dis[line[j].e])//松弛
{
dis[line[j].e]=dis[line[j].s]+line[j].l;
}
}
}
for(j=0; j<edge; j++)//判断是否有负环
{
if(dis[line[j].s]+line[j].l<dis[line[j].e])//当s到line[j].e的路程小于s到line[j].s加上line[j]的长度时，说明在s ,line[j].s,line[j].e中存在一个负环。
//可以自己画一个三角形，两边之和一定大于第三边，只有存在负环的时候两边之和小于第三边
{
flag=1;
break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
int main()
{
int i,j,k,l,n,m,T;
int x,y,s;
cin>>T;
while(T--)
{
cin>>N>>M>>W;
edge=0;
for(i=0; i<M; ++i)
{
scanf("%d%d%d",&x,&y,&s);//无向图
//if(road[x][y]>s)
//road[x][y]=road[y][x]=s;
line[edge].s=x-1;
line[edge].e=y-1;
line[edge].l=s;
edge++;
line[edge].e=x-1;
line[edge].s=y-1;
line[edge].l=s;
edge++;
}
for(i=0; i<W; i++)
{
scanf("%d%d%d",&x,&y,&s);//虫洞
line[edge].s=x-1;
line[edge].e=y-1;
line[edge].l=-s;
edge++;
}
bellman_ford(0);//存在负环使得A-B-A的距离为负
}
return 0;
}