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

## AC (/≧▽≦)/

Posted by 1243295518 at 2019-02-27 13:34:50 on Problem 2457
```#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<map>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#define inf 99999999
using namespace std;
int n,m,e[1010][1010],d[1010],a,b,vis[1010];
stack<int> st;
void init()
{
for(int i=1;i<=n;i++)
{
d[i]=i==1?0:inf;
for(int j=1;j<=n;j++)
e[i][j]=i==j?0:inf;
}
}
void input()
{
for(int i=1;i<=m;i++)
{
cin>>a>>b;
e[a][b]=1;
}
}
void dijkstra()
{
for(int i=1;i<=n;i++)
{
int mins=inf,x;
for(int j=1;j<=n;j++) if(!vis[j]&&d[j]<mins)mins=d[x=j];
vis[x]=1;
for(int j=1;j<=n;j++) d[j]=min(d[j],d[x]+e[x][j]);
}
}
void print()
{
if(d[n]>9999999)
{
cout<<-1;
return;
}
st.push(n);
for(int i=n;i!=1;)
{
for(int j=1;j<=n;j++)
if(e[j][i]&&d[i]==d[j]+e[j][i])st.push(i=j);
}
cout<<st.size()<<endl;
while(!st.empty())
{
cout<<st.top()<<endl;
st.pop();
}
}
int main()
{
cin>>m>>n;//边，点
init();
input();
dijkstra();
print();
}```

Followed by:

User ID:
Title:

Content: