刚开始是用的邻接矩阵，一直wa，后来看了其他人的代码，又想了想，两个点之间有多条路径，不能只存储权值最小的，因为每个路径都可能是一个最短路的组成部分（但现在还不是想的太清楚），所以有多少条边，就存多少边的信息bellman-ford
#include <iostream>
using namespace std;
const int maxn=501;
const int inf=2<<20;
int d[maxn],w[maxn*maxn],u[maxn*maxn],v[maxn*maxn];
int f,n,m,wm,t;
bool bellman()
{
int i,j;
for(i=1;i<=n;i++)
d[i]=inf;
d[1]=0;
for(i=1;i<n;i++)
{
for(j=1;j<=t;j++)
{
if(d[v[j]]>(d[u[j]]+w[j]))
d[v[j]]=d[u[j]]+w[j];
}
}
for(i=1;i<=t;i++)
{
if(d[v[i]]>(d[u[i]]+w[i]))
return true;
}
return false;
}
int main()
{
cin>>f;
while(f--)
{
cin>>n>>m>>wm;
int i;
int tu,tv,tw;
t=0;
for(i=1;i<=m;i++)
{
cin>>tu>>tv>>tw;
t++;
u[t]=tu;v[t]=tv;w[t]=tw;
t++;
u[t]=tv;v[t]=tu;w[t]=tw;
}
for(i=1;i<=wm;i++)
{
cin>>tu>>tv>>tw;
t++;
u[t]=tu;v[t]=tv;w[t]=-tw;
}
bool flag=bellman();
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}