dijstra+输出路径总结

#include<iostream>

#include<math.h>

#include<memory.h>

using namespace std;

#define inf 0x3f3f3f3f

int n,m;//n现有城镇数目，m道路数目

int map[][];

int dis[],vis[];

int path[];

void dijkstra(int a,int b)

{

    int i,j,k,minn;

    for(i=;i<n;i++)

    {

        dis[i]=map[a][i];

        vis[i]=;

        path[i]=a;

    }

    vis[a]=;

    for(i=;i<n;i++)

    {

        minn=inf;

        for(j=;j<n;j++)

        {

            if(vis[j]==&&dis[j]<minn)

            {

                k=j;

                minn=dis[j];

            }

        }

        vis[k]=;

        for(j=;j<n;j++)

        {

            if(vis[j]==&&dis[j]>dis[k]+map[k][j])

            {

                dis[j]=dis[k]+map[k][j];

                path[j]=k;  //j是从k过来的

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int a,b,x,s,e;

        memset(map,inf,sizeof(map));

        for(int i=;i<m;i++)

        {

            cin>>a>>b>>x;

            if(map[a][b]>x)//城镇之间道路不止一条

            map[a][b]=map[b][a]=x;

        }

        cin>>s>>e;

        dijkstra(s,e);

        int p[],k=,temp=e; //输出路径

        while(temp!=s)

        {

            p[k++]=temp;  //一开始p[0]=终点

            temp=path[temp]; //倒着来，是谁推向temp的

        }

        p[k]=s;

        for(int i=k;i>;i--)

            cout<<p[i]<<" ";

        cout<<p[]<<endl;

    }

 }