SPFA判負(fù)權(quán)回路。
以下是我的代碼：
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(507);
const int kMaxm(5207);
const long long kInf(0x7f7f7f7f7f7f7f7fll);
struct Edge
{
int v,w;
};
int n,m,w;
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];
void AddEdge(int u,int v,int w)
{
cnt++;
e[cnt].v=v;e[cnt].w=w;
next[cnt]=first[u];
first[u]=cnt;
}
bool SPFA()
{
long long dist[kMaxn];
queue<int> q;
int num[kMaxn]={0};
bool inq[kMaxn]={false};
for(int i=1;i<=n;i++)
dist[i]=(i==1?0:kInf);
q.push(1);
inq[1]=true;
num[1]++;
while(!q.empty())
{
int u(q.front());q.pop();
inq[u]=false;
if(num[u]>n)
return true;
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v),w(e[i].w);
if(dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
if(!inq[v])
{
q.push(v);
inq[v]=true;
num[v]++;
}
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&w);
cnt=0;
memset(first,-1,sizeof(first));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
for(int i=1;i<=w;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,-w);
}
if(SPFA())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
posted on 2011-07-31 09:51
lee1r 閱讀(245)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論