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 |
SPFA过的,见好多人SPFA不过。。。贴下代码。。#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 1010 using namespace std; typedef struct STA{ int to,len; STA *next; }STA; STA *s[MAX],node[MAX*200]; int n,cou; void init() { memset(s,'\0',sizeof(s)); memset(node,'\0',sizeof(node)); cou = 0; } void Add(int u,int v,int len) { node[cou].to = v; node[cou].len = len; node[cou].next = s[u]; s[u] = &node[cou++]; } int SPFA() { queue<int> Q; int i,len,to,x,inq[MAX],times[MAX],dis[MAX]; STA *head; memset(inq,0,sizeof(inq)); memset(times,0,sizeof(times)); for(i=0; i<=n; i++) dis[i] = INT_MAX; Q.push(0); inq[0] = times[0] = 1; dis[0] = 0; while( !Q.empty() ) { x = Q.front(); Q.pop(); inq[x] = 0; head = s[x]; while( head != NULL ) { to = head->to; len = head->len; if( dis[to] > dis[x] + len ) { dis[to] = dis[x] + len; if( !inq[to] ) { Q.push(to); inq[to] = 1; times[to]++; if( times[to] > n ) return -1; } } head = head->next; } } return 0; } int main() { char ch; int m,i,ans,from,to,len; while( scanf("%d%d",&n,&m) != EOF ) { init(); while(m--) { getchar(); scanf("%c",&ch); if( ch == 'P' ) { scanf("%d%d%d",&from,&to,&len); Add(to,from,len); Add(from,to,-len); } if( ch == 'V' ) { scanf("%d%d",&from,&to); Add(from,to,-1); } } for(i=1; i<=n; i++) Add(0,i,0); //因为下标与在左在右没啥关系,所以只需和源点联系即可。 ans = SPFA(); if( ans == -1 ) printf("Unreliable\n"); else printf("Reliable\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator