| ||||||||||
| 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