尝试了两种判负环方法

DFS_SPFA 为 TLE on #8 #9 #11

BFS_SPFA 为 TLE on #8 #9, WA on #11

code:

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
// #define int long long
using namespace std;
int read(){
  int s = 0, w = 1;
  char c = getchar();
  while(c < '0' || c > '9'){
    if(c == '-')w = -1;
    c = getchar();
  }
  while(c >= '0' && c <= '9'){
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * w;
}
void print(long long x){
  if(x < 0){
    putchar('-');
    x = -x;
  }
  if(x >= 10)print(x / 10);
  putchar(x % 10 + '0');
  return;
}
const int NMax = 3e3;
const int MMax = 6e3;
int n, m;
struct Edge{
  int v, w, next;
}g[MMax + 10], g1[NMax + MMax + 10];
int h[NMax + 10], h1[NMax + 10];
int cnt, cnt1;
void addedge1(int u, int v){
  g1[++cnt1] = (Edge) {v,0,h1[u]};
  h1[u] = cnt1;
}
void addedge2(int u, int v, int w){
  g[++cnt] = (Edge) {v,w,h[u]};
  g1[++cnt1] = (Edge) {v,w,h1[u]};
  h[u] = cnt, h1[u] = cnt1;
}
int sp[NMax + 10], dis[NMax + 10][NMax + 10];

int vis[NMax + 10];
signed main(){
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
  n = read(), m = read();
  for(int i = 1; i <= n; i++){
    addedge1(0, i);
  }
  for(int i = 1; i <= m; i++){
    int u = read(), v = read(), w = read();
    addedge2(u, v, w);
  }
  queue<int>q;
  q.push(0);
  memset(sp, 0x7f, sizeof(sp));
  sp[0] = 0;
  queue<int>que;
  que.push(0);
  while(!que.empty()){
    int u = que.front(); que.pop();
    for(int i = h1[u]; i; i = g1[i].next){
      int& v = g1[i].v, & w = g1[i].w;
      if(sp[v] > sp[u] + w){
        if(++vis[v] > n){ puts("-1"); exit(0); }
        sp[v] = sp[u] + w;
        que.push(v);
      }
    }
  }
  memset(dis, 0x7f, sizeof(dis));
  int inf = dis[0][0];
  for(int s = 1; s <= n; s++){
    priority_queue<pair<int, int> >q;
    dis[s][s] = 0;
    q.push(make_pair(0, s));
    while(!q.empty()){
      int u = q.top().second; q.pop();
      for(int i = h[u]; i; i = g[i].next){
        int& v = g[i].v, & w = g[i].w;
        if(dis[s][v] > dis[s][u] + w + sp[u] - sp[v]){
          dis[s][v] = dis[s][u] + w + sp[u] - sp[v];
          q.push(make_pair(-dis[s][v], v));
        }
      }
    }
  }
  for(int i = 1; i <= n; i++){
    long long ans = 0;
    for(int j = 1; j <= n; j++){
      if(dis[i][j] == inf)ans += j * 1e9;
      else ans += j * (dis[i][j] + sp[j] - sp[i]);
    }
    print(ans), putchar('\n');
  }
  return 0;
}