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+静态链接表,32MS

Posted by speedcell4 at 2011-08-23 19:11:02 on Problem 3268
#include<iostream>
#include<queue>

using namespace std;

#define SIZE 100012

struct node
{
    int v;
    int w;
}edge1[SIZE],edge2[SIZE];
int pre1[SIZE],next1[SIZE];
int pre2[SIZE],next2[SIZE];

class AdjList
{
    public:
        int  Index;
        int  *pre;
        int  *next;
        node *edge;
        AdjList(node *a,int *b,int *c)
        {
            edge=a;
            pre=b;
            next=c;
            clear();
        }
        void clear(void)
        {
            Index=0;
            memset(pre,-1,sizeof(pre)*SIZE);
            memset(next,-1,sizeof(next)*SIZE);
        }
        void add(int u,int v,int w)
        {
            edge[Index].v=v;
            edge[Index].w=w;
            next[Index]=pre[u];
            pre[u]=Index++;
        }
        void printInfo(void)
        {
            for(int i=0;Index-i>0;i++)
            {
                for(int j=pre[i];j!=-1;j=next[j])
                {
                    printf("(%d,%d)=%d   ",i,edge[j].v,edge[j].w);
                }
                printf("\n");
            }
        }
};

int n,m,x;
int a,b,t;
AdjList map1(edge1,pre1,next1);
AdjList map2(edge2,pre2,next2);
int dist[SIZE];
bool inqueue[SIZE];
queue<int> open;

void Init(int s0)
{
    open.push(s0);
    memset(inqueue,false,sizeof(inqueue));
    memset(dist,0x7f,sizeof(dist)); dist[s0]=0;
}
void SPFA(AdjList a,int s0)
{
    Init(s0);
    while(!open.empty())
    {
        int u=open.front(); open.pop(); inqueue[u]=false;
        for(int i=a.pre[u];i!=-1;i=a.next[i])
        {
            int v=a.edge[i].v;
            int w=a.edge[i].w;
            if(dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                if(inqueue[v]==false)
                {
                    inqueue[v]=true;
                    open.push(v);
                }
            }
        }
    }
}
int Count[SIZE]={0};
int findAns(int s0)
{
    memset(Count,0,sizeof(Count));
    SPFA(map1,s0); for(int i=0;n-i>0;i++) Count[i]+=dist[i];
    SPFA(map2,s0); for(int i=0;n-i>0;i++) Count[i]+=dist[i];
    int ans=0;
    for(int i=0;n-i>0;i++)
    {
        ans=max(ans,Count[i]);
    }
    return ans;
}
int main()
{
    map1.clear();
    map2.clear();
    scanf("%d %d %d",&n,&m,&x);
    for(int i=0;m-i>0;i++)
    {
        scanf("%d %d %d",&a,&b,&t);
        map1.add(a-1,b-1,t);
        map2.add(b-1,a-1,t);
    }
    printf("%d\n",findAns(x-1));   
    //system("pause");
    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