| ||||||||||
| 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 600+ms水过 队列还是用stl方便#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int inf=10000000;
int first[1020],nxt[300100],from[300100],to[300100],len[300100],dis[1020],tot,n;
void add(int u,int v,int l)
{
from[tot]=u;
to[tot]=v;
len[tot]=l;
nxt[tot]=first[u];
first[u]=tot++;
}
bool spfa(int s)
{
queue<int>q;
bool vis[1020];
int cnt[1010];
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
for(int i=0;i<=1000;i++)
dis[i]=inf;
dis[s]=0;
vis[s]=1;
cnt[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
vis[u]=0;
q.pop();
for(int i=first[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(dis[v]>dis[u]+len[i])
{
dis[v]=dis[u]+len[i];
if(!vis[v])
{
vis[v]=1;
cnt[v]++;
if(cnt[v]>n)
return false;
q.push(v);
}
}
}
}
return true;
}
int main()
{
int m,a,b,c;
char ch[2];
while(cin>>n>>m)
{
memset(first,-1,sizeof(first));
tot=0;
while(m--)
{
scanf("%s",&ch);
if(ch[0]=='P')
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
add(b,a,c);
}
else
{
scanf("%d%d",&a,&b);
add(a,b,-1);
}
}
for(int i=1;i<=n;i++)
add(0,i,0);
if(!spfa(0)) puts("Unreliable");
else puts("Reliable");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator