求助大佬，程式過不了
輸入的第一行是一個整數 T，表示測驗資料的組數。對于每組資料的格式如下：
第一行有兩個整數，分別表示圖的點數 n 和接下來給出邊資訊的條數 m。
接下來 m 行，每行三個整數 u,v,w。
若 w≥0，則表示存在一條從 u 至 v邊權為 w 的邊，還存在一條從 v 至 u 邊權為 w 的邊。
若 w<0，則只表示存在一條從 u 至 v 邊權為 w 的邊。
代碼：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 100000 + 5;
int n,m,s;
struct Edge
{
int v,w;
};
vector<Edge> g[maxn];
int dis[maxn],cnt[maxn];
bool inq[maxn],tmp;
void SPFA(int s)
{
queue<int> que;
memset(cnt,0,sizeof(cnt));
memset(dis,0x3f,sizeof(dis));
memset(inq,false,sizeof(inq));
dis[s] = 0;
inq[s] = true;
que.push(s);
while(!que.empty())
{
int u = que.front();
que.pop();
inq[u] = false;
for(int i = 0;i < g[u].size();i++)
{
int v = g[u][i].v,w = g[u][i].w;
if(dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
if(!inq[v]) que.push(v);
if(++cnt[v] > n)
{
tmp = 1;
return;
}
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int i,u,v,w;
cin>>n>>m;
while(m--)
{
cin>>u>>v>>w;
g[u].push_back((Edge){v,w});
if(w >= 0) g[v].push_back((Edge){u,w});
}
for(i = 1;i <= n;i++)
{
if(tmp) break;
SPFA(i);
}
if(tmp) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
tmp = false;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256895.html
標籤：C++ 語言
上一篇：【求助】函式指標和結構體
下一篇：來位大佬，學校的OJ題目ac不過