```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 2147483647
using namespace std;
struct edge{
int from,to,value;
void Init(int a,int b,int c)
{
this->from=a,this->to=b,this->value=c;
}
}Edge[40001];
int dis[10001],n,m,cnt=1,t;
bool flag=false;
int main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w+",stdout);
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
for (register int i=2;i<=n;i++)
{
dis[i]=INF;
}
dis[1]=0;
for (register int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Edge[i].Init(a,b,c);
}
for (register int i=1;i<=n-1;i++)
{
for (register int j=1;j<=m;j++)
{
if (dis[Edge[j].from]+Edge[j].value<dis[Edge[j].to])
{
dis[Edge[j].to]=dis[Edge[j].from]+Edge[j].value;
}
}
}
for (register int i=1;i<=m;i++)
{
if (dis[Edge[i].from]+Edge[i].value<dis[Edge[i].to])
{
flag=true;
}
}
if (flag)puts("YE5");
else puts("N0");
}
return 0;
}
```
by Jelly_Goat @ 2019-03-05 17:53:44
求救啊~救命啊
by Jelly_Goat @ 2019-03-05 17:54:08
如果和答案不相反你不就A了吗……?
by 皎月半洒花 @ 2019-03-05 17:54:11
@[_皎月半洒花](/space/show?uid=28313)
你看看[这个](https://www.luogu.org/recordnew/show/16911729)
反过来了嘤嘤嘤......
by Jelly_Goat @ 2019-03-05 18:02:13
@[Jelly_Goat](/space/show?uid=122927)
大佬,有负环没有最短路吧.......
by 隐隐约约妖艳 @ 2019-03-05 18:04:58
@[Jelly_Goat](/space/show?uid=122927) tql
by AntiO2 @ 2019-03-05 18:28:20
@[Jelly_Goat](/space/show?uid=122927)
正权边是无向的
而且要判断是否与1号节点连通
by lemondinosaur @ 2019-03-05 18:30:43
没卡,我就是用Bellman-Ford做的
by lemondinosaur @ 2019-03-05 18:31:06
与楼主感同深受
by lzxy @ 2019-03-05 18:33:28
@[SSL_XJQ_逐风之刃](/space/show?uid=37782)
您的意思是两侧都要加上一条边?
我试试......
by Jelly_Goat @ 2019-03-06 17:18:16