你古词典:spfa，象征着死亡，当时出题人直接说会被卡。
~~ptwa~~
by chenhongyu20100506 @ 2022-07-31 10:40:14
@[liangbowen](/user/367488)
改好了，但样例输出 -2 -5 -7？
我还有什么错吗，找不出来了qwq
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,T,vis[100005],ind,vFirst[100005],dis[100005],tim[100005];
struct Edge{
int v,w,next;
}e[100005];
void add(int u,int v,int w)
{
ind++;
e[ind].v=v;
e[ind].w=w;
e[ind].next=vFirst[u];
vFirst[u]=ind;
}
bool SPFA()
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(1);
vis[1]=1;
int u,v;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=0;
for(int i=vFirst[u];i!=-1;i=e[i].next)
{
v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[e[i].v]=dis[u]+e[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=1;
tim[v]++;
if(tim[v]>=n)
{
return true;
}
}
}
}
}
return false;
}
int main()
{
memset(vFirst,-1,sizeof(vFirst));
memset(vis,0,sizeof(vis));
memset(tim,0,sizeof(tim));
cin>>n>>m;
for(int j=1;j<=m;j++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for (int i = 1; i <= n; i++) add(0, i, 0);
if(!SPFA())
{
cout<<"-1";
}
else
{
for(int i=1;i<=n;i++)
{
cout<<dis[i]<<' ';
}
}
return 0;
}
```
by Level_1024 @ 2022-07-31 10:41:21
楼上为搞笑内容
~~JRBG~~
by chenhongyu20100506 @ 2022-07-31 10:41:47
发错了。再发一遍
by Level_1024 @ 2022-07-31 10:41:51
看题解（（
by liangbowen @ 2022-07-31 10:41:52
只要满足不等式即可，不一定要和样例一模一样
@[codingxile](/user/377794)
by _JF_ @ 2022-07-31 10:43:40
删掉add（u,v,w）后，就输出-1了
三角不等式就是两边之和大于第3边吧（？
by Level_1024 @ 2022-07-31 10:44:12
并且好像不用连双向边吧....
by _JF_ @ 2022-07-31 10:44:35
@[_JF_](/user/361141)
删掉之后就输出-1了
by Level_1024 @ 2022-07-31 10:45:12
@[liangbowen](/user/367488)
by Level_1024 @ 2022-07-31 10:45:25