邻接表 + SPFA 76pts，求优化

#include <bits/stdc++.h>
using namespace std;
const int N = 2010,INF = 0x3f3f3f3f;
int t,n,m;
int g[N][N];
int d[N],cnt[N];
bool st[N];
bool spfa() {   
    for(int i = 1;i <= n;i++) {cnt[i] = st[i] = 0;d[i] = INF;}
    queue<int> q;
    d[1] = 0;
    st[1] = 1;
    q.push(1);
    while(q.size()) {
        int fr = q.front();
        q.pop();
        st[fr] = 0;
        for(int i = 1;i <= n;i++) {
            if(g[fr][i] == INF) continue;

            if(d[fr] + g[fr][i] < d[i]) {
                d[i] = d[fr] + g[fr][i];
                cnt[i] = cnt[fr] + 1;
                if(cnt[i] >= n) return true;
                if(!st[i]) {
                    st[i] = 1;
                    q.push(i);
                }
            }
        }
    }

    return false;
}
int main(){
    cin >> t;
    while(t--) {
        cin >> n >> m;
        memset(g,0x3f,sizeof(g));
        while(m--) {
            int a,b,c;
            cin >> a >> b >> c;
            if(c >= 0) g[b][a] = g[a][b] = min(c,g[a][b]);
            else g[a][b] = min(c,g[a][b]);
        }

        if(spfa()) cout << "YES" << endl;
        else cout << "NO" << endl; 
    }

    
    return 0;
}