按照正常的推导，差分约束系统转化成图之后求最短路得到应该的是最大可行解，但为什么我这份代码跑 P5960 【模板】差分约束算法 的样例得到的答案会比样例还要小？

代码能过，但还是有疑惑。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],w[M],ne[M],idx;
int n,m,s;
int dis[N],st[N],cnt[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool SPFA(int s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    queue<int> q;
    q.push(s);
    st[s]=1;cnt[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        st[u]=0;
        for(int i=h[u];~i;i=ne[i])
        {
            int v=e[i];
            if(dis[v]>dis[u]+w[i])
            {
                dis[v]=dis[u]+w[i];
                if(!st[v]) q.push(v),cnt[v]++,st[v]=1;
                if(cnt[v]>n+1) return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(b,a,c);
    }
    for(int i=1;i<=n;i++) add(0,i,0);
    if(SPFA(0)) printf("NO");
    else for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}