Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

SPFA过的,见好多人SPFA不过。。。贴下代码。。

Posted by zxy_snow at 2011-02-06 19:32:34 on Problem 2983
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator