最短路

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define maxm 50005 #define maxn 1005 struct Edge {
    int v, next; }edge[maxm * 2]; int n, m; int head[maxn]; int ecount; int from[maxn]; int q[maxn]; int stk[maxn]; bool vis[maxn]; void addedge(int a, int b) {
        edge[ecount].v = b;     edge[ecount].next = head[a];     head[a] = ecount++; } void input() {
        scanf("%d%d", &m, &n);     ecount = 0;     memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++)     {
    int a, b;         scanf("%d%d", &a, &b);         a--;         b--;         addedge(a, b);     } } void bfs() {
        memset(vis, 0, sizeof(vis)); int front = 0; int rear = 0;     q[rear++] = 0;     vis[0] = true; while (front != rear)     {
    int u = q[front++]; for (int i = head[u]; i != -1; i = edge[i].next)         {
    int v = edge[i].v; if (!vis[v])             {
                    from[v] = u;                 q[rear++] = v;                 vis[v] = true; if (v == n - 1) return;             }         }     } } void print() {
    int a = n - 1; int top = 0; while (a != 0)     {
            stk[top++] = a;         a = from[a];     }     stk[top++] = 0;     printf("%d\n", top); for (int i = top - 1; i >= 0; i--)         printf("%d\n", stk[i] + 1); } int main() {
    //freopen("t.txt", "r", stdin);     input();     bfs(); if (!vis[n - 1])         printf("-1\n"); else         print(); return 0; }