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

用Vector 实现伪邻接表然后SPFA。忘了 clear()贡献一发WA。

Posted by dongshimou at 2014-07-21 09:51:06 on Problem 1125
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
struct lx
{
    int v,len;
};
vector<lx>g[101];
int n,m;

int SPFA(int start)
{
    queue<int>q;
    int dis[101];
    bool vis[101];
    for(int i=1;i<=n;i++)
        dis[i]=INF,vis[i]=0;
    q.push(start);
    dis[start]=0,vis[start]=1;

    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].v;
            int len=g[u][j].len;
            if(dis[v]>dis[u]+len)
            {
                dis[v]=dis[u]+len;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dis[i]);
//        printf("%d->%d:%d==\n",start,i,dis[i]);
    }
    return ans;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<=n;i++)
        {
            int v,len;
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d%d",&v,&len);
                lx now;
                now.v=v,now.len=len;
                g[i].push_back(now);
            }
        }
        int ans=INF;
        int s=1;
        for(int i=1;i<=n;i++)
        {
            int tmp=SPFA(i);
            if(tmp<ans)
            {
                ans=tmp;
                s=i;
            }
        }
        if(ans==INF)
            puts("disjoint");
        else
            printf("%d %d\n",s,ans);
    }
}

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