最短路记录路径——PKU 2457

DIJK水过

#include<stdio.h>
#include<string.h>
#include<stack>
#include<iostream>
using namespace std;

int n,m;
int map[1009][1009];
int path[1009];
int dis[1009];
bool used[1009];
const int maxint=999999999;

void dijk()
{
    memset(path,-1,sizeof(path));
    memset(used,0,sizeof(used));
    int i,j,k;
    used[1]=1;

    for(i=1;i<=n;i++)
        dis[i]=map[1][i];

    for(i=1;i<n;i++)
    {
        int tmin=maxint;
        for(j=1;j<=n;j++)
        {
            if(used[j]==0&&tmin>dis[j])
            {
                tmin=dis[j];k=j;
            }
        }

        used[k]=1;
        for(j=1;j<=n;j++)
        {
            if(used[j]==0)
            {
                if(dis[k]+map[k][j]<dis[j])
                {
                    dis[j]=dis[k]+map[k][j];
                    path[j]=k;
                }
            }
        }
    }

    stack<int>ss;
    ss.push(n);
    i=n;
    while(path[i]!=-1)
    {
        i=path[i];
        ss.push(i);
    }
    if(dis[n]==maxint)
    {
        printf("-1\n");
        return ;
    }
    ss.push(1);
    printf("%d\n",dis[n]+1);
    
    while(!ss.empty())
    {
        printf("%d\n",ss.top());
        ss.pop();
    }
}

int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                map[i][j]=maxint;
        }
        
        int a,b;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        
        dijk();
    }
}