模板-PA1030二标尺最优路径并打印路径

/*Dijkstra+DFS解法

Dijkstra(st)
DFS(ed)
sum(st)
print(st)*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXV=510;
const int INF=100000000;//INF不要用INT_Max,C++有时会判断INT_Max小于0
int minCost=INF;
int n,m,st,ed,G[MAXV][MAXV];//顶点数,边数,起点,终点
int cost[MAXV][MAXV];
int d[MAXV];//d[ed]=x表示从起点到终点的最短距离为x
int num[MAXV];//最短路径数目
bool vis[MAXV]= {false}; //vis[ed]=true表示顶点ed已入树
int k=0;
vector<int> pre[MAXV];//pre[ed]={v1,v2,v3}表示从起点到终点的最短路径有3条,且前驱顶点分别为v1,v2,v3;
int tempPath[MAXV],path[MAXV];

void Dijkstra(int s)//s为起点
{
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0; i<n; i++)
    {
        int u=-1,MIN=INF;
        for(int j=0; j<n; j++)
        {
            if(vis[j]==false&&d[j]<MIN)
            {
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1)//找不到小于INF的d[u],说明剩下的顶点和起点s不连通
            return;
        vis[u]=true;

        //遍历,判断v能否作为中介点
        for(int v=0; v<n; v++)
        {
            if(vis[v]==false&&G[u][v]!=INF)
            {
                if(d[u]+G[u][v]<d[v])
                {
                    d[v]=d[u]+G[u][v];
                    pre[v].clear();//令v的前驱为u
                    pre[v].push_back(u);
                }
                else if(d[u]+G[u][v]==d[v])
                    pre[v].push_back(u);
            }
        }
    }
}

//求边权和
int sum(int v)
{
    int a=0;
    while(v!=ed)
    {
        a+=cost[v][tempPath[v]];
        v=tempPath[v];
    }
    return a;
}

//打印路径(从起点到终点)
void print(int v)
{
    printf("%d",v);
    while(v!=ed)
    {
        printf(" %d",path[v]);
        v=path[v];
    }
}

void DFS(int v)
{
    if(v==st)
    {
        //num++;如果需要统计由Dijkstra算法生成的最短路径数目,就需要这句
        int costSum=sum(v);
        if(costSum<minCost)//假如"当前路径权值和"小于"当前最小路径权值和",则刷新"当前最小路径权值和"
        {
            minCost=costSum;
            memcpy(path,tempPath,sizeof(tempPath));
        }
        return;
    }

    for(int i=0; i<pre[v].size(); i++)//在该题中,pre[3]={1,2};pre[2]={0};pre[1]={0};
    {
        tempPath[pre[v][i]]=v;//比如起点至终点为的一条最短路径为0-1-3，则tempPath[1]=3;tempPath[0]=1;
        DFS(pre[v][i]);
    }
}

int main()
{
    cin>>n>>m>>st>>ed;
    int u,v,l,co;
    fill(G[0],G[0]+MAXV*MAXV,INF);
    fill(cost[0],cost[0]+MAXV*MAXV,INF);
    for(int i=0; i<m; i++)
    {
        cin>>u>>v>>l>>co;
        G[u][v]=G[v][u]=l;
        cost[u][v]=cost[v][u]=co;
    }
    Dijkstra(st);
    DFS(ed);

    print(st);
    printf(" %d %d\n",d[ed],minCost);
}
/*
输入:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出:
0 2 3 3 40
*/