| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
类型打错导致WA n次,附上SPFA邻接表代码,祭奠我的黑眼圈。。#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <cmath>
#include <set>
#include <climits>
#define INF 0x7fffffff
#define finc(i,a,b) for(i=a;i<=b;i++)
#define fdec(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int MAXN=502,MAXM=5205;
int N,M,S,T,W;
double V;
struct Edge //使用数组模拟邻接表存储边信息
{
int a,b;
double r,c;
int next;
}D[MAXM];
int list[MAXN],tot;
double dist[MAXN];
queue<int>q;
int cnt[MAXN];
bool f[MAXN];
void add(int a,int b,double r,double c) //构建邻接表
{
D[++tot].a=a;
D[tot].b=b;
D[tot].c=c;
D[tot].r=r;
D[tot].next=list[a];
list[a]=tot;
}
bool init()
{
int i;
if(cin>>N>>M>>S>>V);
else return false;
for(int i=1;i<=M;i++)
{
int a,b;
double c,r;
cin>>a>>b>>r>>c;
add(a,b,r,c);
cin>>r>>c;
add(b,a,r,c); //如果为有向图则不加此句
}
return true;
}
bool spfa()
{
for(int i=1;i<=N;i++) //初始化距离
dist[i]=0;
dist[S]=V;
q.push(S);f[S]=0;
while(q.size())
{
if(dist[S]>V) return false;
int a=q.front(),b; //取出队首元素
q.pop();
for(int k=list[a]; k; k=D[k].next) //枚举其每条出边进行松弛
{
b=D[k].b;
if(dist[b]<(dist[a]-D[k].c)*D[k].r)
{
dist[b]=(dist[a]-D[k].c)*D[k].r;
if(f[b] == 0)
{
f[b]=1;
q.push(b);
}
cnt[b]++; //记录每个点入队次数
if(cnt[b]>N)
return false; //如果某个点入队超过N次,则有负环
}
}
f[a]=0;
}
return true;
}
int main()
{
while(1){
tot=0;
while(!q.empty()) q.pop();
memset(cnt,0,sizeof(cnt));
memset(list,0,sizeof(list));
memset(f,false,sizeof(f));
if(!init()) break;
if(spfa())
cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator