大概是松弛的时候爆int了。
别用2147483647，用0x3f3f3f.
by Smokey_Days @ 2018-07-01 07:52:40
楼上正解，你的
```cpp
if(dis[i]>dis[s]+road[s][i])
```
这句话不等号右边可能变成负值。
@[ZXZ695](/space/show?uid=59946)
by 北极鹅 @ 2018-07-01 08:00:05
改了好久，还是WA...@[北极鹅](/space/show?uid=29277)
@[Smokey_Days](/space/show?uid=97512)
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long int n,m,road[1005][1005],q[300015],dis[1005],flag[1005];
long int x[100005],y[100005],z[100005];
void star()
{
memset(dis,0x3f3f3f,sizeof(dis));;
}
void scan1()
{
scanf("%ld%ld",&n,&m);
memset(road,0x3f3f3f,sizeof(road));
for(int i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&x[i],&y[i],&z[i]);
road[x[i]][y[i]]=z[i];
}
}
void scan2()
{
memset(road,0x3f3f3f,sizeof(road));
for(long int i=1;i<=m;i++)
road[y[i]][x[i]]=z[i];
}
long int print()
{
long int tot=0;
for(long int i=2;i<=n;i++)
tot+=dis[i];
return tot;
}
void Spfa()
{
q[1]=1;
dis[1]=0;
flag[1]=1;
long int s;
long int head=0,tail=1;
while(head<tail)
{
head++;
s=q[head];
flag[s]=0;
for(long int i=1;i<=n;i++)
{
if(i==s)continue;
if(road[s][i]>10000)continue;
if(dis[i]>dis[s]+road[s][i])
{
dis[i]=dis[s]+road[s][i];
if(!flag[i])
{
tail++;
q[tail]=i;
flag[i]=1;
}
}
}
}
}
int main()
{
star();
scan1();
Spfa();
long int ans1=0;
ans1=print();
memset(flag,0,sizeof(flag));
memset(q,0,sizeof(q));
long int ans2=0;
scan2();
star();
Spfa();
ans2=print();
printf("%ld",(ans1+ans2));
}
```
by ZXZ695 @ 2018-07-01 11:43:06