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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

水水水~~~

Posted by 15310320305 at 2017-02-07 13:53:56 on Problem 2457
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

int n,m,e;
int hed[1005],vis[1005],pre[1005],dis[1005];

struct st{
    int v,w,nex;
}edge[100005];

void add(int u,int v,int w){
    edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
}
int spfa(){
    for(int i=1;i<=n;i++)dis[i]=1e8,vis[i]=0,pre[i]=i;
    vis[1]=1,dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int u = q.front();q.pop();vis[u]=0;
        for(int i=hed[u];~i;i=edge[i].nex){
            int v = edge[i].v;
            if(dis[v]>dis[u]+edge[i].w){
                dis[v]=dis[u]+edge[i].w;
                pre[v]=u;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return (dis[n]==1e8?-1:dis[n]+1);
}

void dfs(int s){
    if(pre[s]!=s)
        dfs(pre[s]);
    printf("%d\n",s);
}

int main()
{
    cin>>m>>n;
    memset(hed,-1,sizeof(hed));
    e=1;
    while(m--){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v,1);
    }
    int ans = spfa();
    cout<<ans<<endl;
    if(ans!=-1){
        dfs(n);
    }
    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