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 600+ms水过 队列还是用stl方便

Posted by zengshiyuan at 2014-08-02 11:20:18 on Problem 2983
#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:
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