图论--最短路--Floyd（含路径输出）

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define maxn 1005

int D[maxn][maxn];

int P[maxn][maxn];

int N,M;  //顶点数边数

int S,E;  //起点终点

void Floyd()

{

    for(int k=1;k<=N;k++)

        for(int i=1;i<=N;i++)

            for(int j=1;j<=N;j++)

            {

                if(D[i][j]>D[i][k]+D[k][j])

                {

                    D[i][j]=D[i][k]+D[k][j];

                    P[i][j]=P[k][j];

                }

            }

}

int main()

{

    //init

    memset(D,0x3f,sizeof(D));

    memset(P,0x3f,sizeof(P));

    //录入图

    cin>>N>>M;

    for(int i=1;i<=M;i++)

    {

        int u,v,cost;

        cin>>u>>v>>cost;

        if(cost<D[u][v])  //D的初始化为边的信息

        {

            D[u][v]=cost;

            //D[v][u]=cost;//无向图

        }

    }

    for(int i=1;i<=N;i++)   //初始化P

        for(int j=1;j<=N;j++)

        {

            if(i!=j&&D[i][j]!=INF)  //P第0层为i

                P[i][j]=i;

        }

    cin>>S>>E;

    //

    Floyd();

    //最短距离

    cout<<D[S][E]<<endl;

    //路径回溯

    int temp=P[S][E];

    cout<<E;

    while(true)

    {

        if(temp==S)

        {

            cout<<"<--"<<S<<endl;

            break;

        }

        cout<<"<-"<<P[S][temp];

        temp=P[S][temp];

    }

}
巴特西

图论--最短路--Floyd（含路径输出）

最新文章

热门文章
