PAT甲级1030 Travel Plan (30分)|C++实现

一、题目描述

原题链接
A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

​​Output Specification:

Sample Input:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Sample Output:

0 2 3 3 40

二、解题思路

一道Dijkstra算法题，基本上套用格式就好了，只是在路程相同的情况下，我们要追加判断路线的花销，我们优先选择花销最小的路。我们可以用pre数组来表示该点的前一个点。但是需要注意的是，如果我们使用pre数组，则意味着我们只能从后往前输出，若要从前往后输出，则可以使用堆栈的思想，也即使用递归，在这里我并不太确定这能不能叫dfs…姑且用了这个名字命名，还望指正。

三、AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXV = 510;
const int INF = 1000000000;
int n, m, st, ed, G[MAXV][MAXV], cost[MAXV][MAXV];
int d[MAXV], c[MAXV], pre[MAXV];
bool vis[MAXV] = {false};

void Dijkstra(int s)
{
    fill(d, d+MAXV, INF);
    fill(c, c+MAXV, INF);
    for(int i=0; i<n; i++)  pre[i] = i;
    d[s] = 0;
    c[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) return;
        vis[u] = true;
        for(int v=0; v<n; v++)
        {
            if(vis[v] == false && d[u] + G[u][v] != INF)
            {
                if(d[u] + G[u][v] < d[v])
                {
                    d[v] = d[u] + G[u][v];
                    c[v] = c[u] + cost[u][v];
                    pre[v] = u;
                }
                else if(d[u] + G[u][v] == d[v])
                {
                    if(c[u] + cost[u][v] < c[v])
                    {
                        c[v] = c[u] + cost[u][v];
                        pre[v] = u;
                    }
                }
            }
        }
    }
}

void DFS(int v)
{
    if(v == st)
    {
        printf("%d ", v);
        return;
    }
    DFS(pre[v]);
    printf("%d ", v);
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    int u, v;
    fill(G[0], G[0]+MAXV*MAXV, INF);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d", &u, &v);
        scanf("%d%d", &G[u][v], &cost[u][v]);
        G[v][u] = G[u][v];
        cost[v][u] = cost[u][v];
    }
    Dijkstra(st);
    DFS(ed);
    printf("%d %d\n", d[ed], c[ed]);
    return 0;
}