Source Code
//想知道怎样再这个基础上优化内存，离大牛们的水平还很远阿
Problem: 3268  User: dut200901102 
Memory: 840K  Time: 0MS 
Language: G++  Result: Accepted 

Source Code 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
//spfa + queue + 数组模拟邻接表
using namespace std;

const int MAXN=1001;
const int MAXM=100001;
const int INF=2000000001;

struct edge{
    int to,weigh,next;
}edges1[MAXM],edges2[MAXM];
int box1[MAXN],box2[MAXN];

int n,m,x;
int d[MAXN];

void spfa(int start,edge edges[],int box[])
{
    int i,k,u;
    bool flag[MAXN];
    queue < int > que;
    memset(flag,false,sizeof(flag));
    for(i=1;i<=n;++i)
    {
        d[i]=INF;
    }
    d[start]=0;
    que.push(start);
    flag[start]=true;
    while(!que.empty())
    {
        k=que.front();
        que.pop();
        flag[k]=false;
        for(i=box[k];i!=-1;i=edges[i].next)
        {
            u=edges[i].to;
            if(d[u]-edges[i].weigh>d[k])
            {
                d[u]=d[k]+edges[i].weigh;
                if(!flag[u])
                {
                    que.push(u);
                    flag[u]=true;
                }
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int i,a,b,v,max;
    int ans[MAXN];
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
    {
        memset(box1,-1,sizeof(box1));
        memset(box2,-1,sizeof(box2));
        for(i=0;i<m;++i)
        {
            scanf("%d%d%d",&a,&b,&v);
            edges1[i].to=b;
            edges1[i].weigh=v;
            edges1[i].next=box1[a];
            box1[a]=i;
            edges2[i].to=a;
            edges2[i].weigh=v;
            edges2[i].next=box2[b];
            box2[b]=i;
        }
        spfa(x,edges1,box1);
        for(i=1;i<=n;++i)
        {
            ans[i]=d[i];
        }
        spfa(x,edges2,box2);
        for(i=1;i<=n;++i)
        {
            ans[i]+=d[i];
        }
        max=1;
        for(i=1;i<=n;++i)
        {
            if(ans[i]>ans[max])
            {
                max=i;
            }
        }
        printf("%d\n",ans[max]);
    }
    return 0;
}

• 悲剧啊，相同的代码，c++竟然帮我刷进第一页了，这差距真大啊 (2) dut200901102 2010-10-22 12:25:27