Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 水水水~~~

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];

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);
}
int ans = spfa();
cout<<ans<<endl;
if(ans!=-1){
dfs(n);
}
return 0;
}```

Followed by: