0分TLE求调,spfa,孩子要调疯了orz
查看原帖
0分TLE求调,spfa,孩子要调疯了orz
1107382
Yg2023楼主2024/3/18 22:04

不知道为什么错了qwq,spfa的板子,也认真初始化了,样例和Subtask都过了,其他的就TLE了。

求求dalao帮忙看看,孩子要调疯了orz

#include <iostream>
//#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <vector>
#define ll long long
#define rd read()
#define Max 1e9 + 10
using namespace std;
const int L = 6e3 + 10, Mn = 2e3 + 10;
ll head[L], nxt[L], edge[L], dis[Mn], w[L], vis[Mn], now = 0, cnt[Mn];
ll n;
ll read(void)
{
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - '0'; c = getchar();
    }
    return f * res;
}
void addEdge(ll u, ll v, ll x)
{
    edge[++now] = v;
    w[now] = x;
    nxt[now] = head[u];
    head[u] = now;
}
bool spfa()
{
    queue<ll> q;
    q.push(1);
    dis[1] = 0;
    vis[1] = 1;
    while(!q.empty())
    {
        ll pos = q.front(); q.pop();
        vis[pos] = 0;
        for(ll i = head[pos]; i; i = nxt[i])
        {
            ll j = edge[i];
            if(dis[j] > dis[pos] + w[i])
            {
                dis[j] = dis[pos] + w[i];
                cnt[j] = cnt[i] + 1;
                if(cnt[j] >= n) return true;
                if(!vis[j])
                {
                    q.push(j); vis[j] = 1;
                }
            }
        }
    }
    return false;
}
int main(){
    ll t, m;
    ll u, v, x;
    cin >> t;
    for(int i = 0; i < t; ++i)
    {
        n = rd; m = rd;
        now = 0;
        for(ll j = 0; j <= L - 10; ++j)
        {
            head[j] = 0;
        }

        //cout << "here" << endl;
        for(int j = 0; j <= Mn - 10; ++j)
        {
            dis[j] = Max;
            vis[j] = 0;
            cnt[j] = 0;
        }
        for(int j = 0; j < m; ++j)
        {
            u = rd; v = rd; x = rd;
            if(x >= 0) addEdge(v, u, x);
            addEdge(u, v, x);
        }
        bool flg = spfa();
        if(flg) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    
    return 0;
}

求求了,谢谢dalao们

2024/3/18 22:04
加载中...