rt，经过一系列输中量的调试之后发现 h 数组的值好像有问题，但是仔细检查了 Belman-Ford 却找不出错

具体来讲，样例 2 可过，样例 1 输出：

116
1000000120
999999956
1000000046
999999992

但是经查 dis 数组的值没问题

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=3e3+10,M=1e4+10,INF=1e9;
int n,m,u,v,w,h[N],dis[N],vis[N];
long long ans;
struct edge{int v,w;edge(int x,int y){v=x,w=y;}};
vector<edge> e[N];

struct node{
    int d,u;
    node(int x,int y){d=x,u=y;}
    bool operator<(const node &b)const{return d>b.d;}
};

bool BellmanFord(int n,int s){
    bool flag;
    for(int i=1;i<=n;i++)h[i]=INF;
    for(int i=1;i<=n;i++){
        flag=0;
        for(int u=0;u<=n;u++){
            if(h[u]==INF)continue;
            for(auto ed:e[u]){
                int v=ed.v,w=ed.w;
                if(h[v]>h[u]+w)
                    h[v]=h[u]+w,flag=1;
            }
        }
        if(!flag)break;
    }
    return flag;
}

void dijkstra(int s){
    priority_queue<node> pq;
    for(int i=1;i<=n;i++)dis[i]=i==s?0:INF,vis[i]=0;
    pq.push(node(0,s));
    while(!pq.empty()){
        int u=pq.top().u;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w)
                dis[v]=dis[u]+w,pq.push(node(dis[v],v));
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>u>>v>>w,e[u].push_back(edge(v,w));
    for(int i=1;i<=n;i++)e[0].push_back(edge(i,0));
    if(BellmanFord(n,0))puts("-1"),exit(0);
    for(int u=1;u<=n;u++)for(auto ed:e[u])
        ed.w+=h[u]-h[ed.v];
    for(int i=1;i<=n;i++){
        ans=0;
        dijkstra(i);
        for(int j=1;j<=n;j++){
//          cout<<dis[j]<<' ';
//          if(i==2&&j==3)cout<<'\n'<<dis[j]+h[j]-h[i]<<'\n';
            if(dis[j]==INF)ans+=1ll*j*INF;
            else ans+=1ll*j*(dis[j]+h[j]-h[i]);
//          cout<<ans<<' ';
        }
        cout<<ans<<"\n";
    }
    return 0;
}

求大佬们帮忙看看，谢谢！