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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么RE= =

Posted by 52hz1 at 2017-05-23 20:18:55 on Problem 2631
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=10005;
const int M=20010;

struct Edge
{
    int v,next,w;

} edge[M];

bool vis[N];
int head[N],dis[N];
int nd,n,i;

void init()
{
    CLR(head,-1);
    nd=n=0;
}

void bfs(int s)
{
    CLR(vis,0),CLR(dis,0);

    queue<int>q;
    q.push(s);
    vis[s]=1;

    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;

            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+edge[i].w;
                q.push(v);
            }
        }
    }
}

void solve()
{
    int ans,x,y;

    ans=0;               //x=s
    bfs(1);
    for(i=1; i<=n; ++i)
        if(dis[i]>ans)
            ans=dis[i],x=i;

    ans=0;
    bfs(x);
    for(i=1; i<=n; ++i)
        if(dis[i]>ans)
            ans=dis[i],y=i;

    printf("%d\n",ans);
}

int main()
{
    int u,v,w;
    init();
    while(~scanf("%d%d%d",&u,&v,&w))
    {
        edge[nd].v=v,edge[nd].next=head[u],edge[nd].w=w,head[u]=nd++;
        edge[nd].v=u,edge[nd].next=head[v],edge[nd].w=w,head[v]=nd++;
        n=max(n,max(u,v));
    }
    solve();

    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