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