不知道为什么错了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们