题目来源：PAT A1030 Travel Plan

题意：

有N个城市(编号0-N-1)，M条道路(无向边)，并给出M条道路的距离属性与花费属性。现在给定起点S和终点D，求从起点到终点的最短路径，最短距离及花费。注意：如果有多条最短路径，则选择花费最小的那条。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 0xfffffff;
const int maxv = 510;

int n, m, s, e; //顶点个数，边数,起点编号，终点编号
int G[maxv][maxv];
int dis[maxv]; //从起点到各点的最短距离
bool vis[maxv] = {false};
int Cost[maxv][maxv];　　//顶点间的花费(边权)
int c[maxv]; //从起点到各点的最小花费(在最短路径下)
vector<int> pre[maxv];  //存放结点的前驱结点
vector<int> path, tempPath;  //最优路径，临时路径
int optValue = INF;  //第二标尺最优值

void Dijkstra(int s)
{
    dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        int u = -1;
        int min = INF;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && dis[j] < min)
            {
                u = j;
                min = dis[j];
            }
        }
        if (u == -1)
        {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++)
        {
            if (vis[v] == false && G[u][v] != INF)
            {
                if (dis[u] + G[u][v] < dis[v])
                {
                    dis[v] = dis[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (dis[u] + G[u][v] == dis[v])
                {
                    if (c[v] > c[u] + Cost[u][v])
                    {
                        c[v] = c[u] + Cost[u][v];
                        pre[v].push_back(u);
                    }
                }
            }
        }
    }
}

void DFS(int v)   //v为当前访问结点
{
    if (v == s)   //如果到达了叶子结点st(即路径的起点)
    {
        tempPath.push_back(v);
        int value;  //边权之和
        for (unsigned int i = tempPath.size() - 1; i > 0; i--)
        {
            int id = tempPath[i];
            int nextid = tempPath[i - 1];
            value += Cost[id][nextid]; //value边增加 id -> nextid的边权
        }
        if (value < optValue)
        {
            optValue = value;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (unsigned int i = 0; i < pre[v].size(); i++)
    {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main()
{
    int u, v, dis1, cost;
    cin >> n >> m >> s >> e;
    fill(G[0], G[0] + maxv * maxv, INF);
    fill(Cost[0], Cost[0] + maxv * maxv, INF);
    fill(dis, dis + maxv, INF);
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> dis1 >> cost;
        G[u][v] = G[v][u] = dis1;
        Cost[u][v] = Cost[v][u] = cost;
    }

    Dijkstra(s);
    DFS(e);
    for (int i = path.size() - 1; i >= 0; i--)
    {
        cout << path[i] << ' ';
    }
    cout << dis[e] << ' ' << optValue << endl;
    return 0;
}
复制