PTA A_1030 Travel Plan

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805464397627392

解：
迪杰斯特拉 + DFS （模板）

#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 510;

int n, m, c1, c2;
int G[maxn][maxn];
int cost[maxn][maxn];
int d[maxn];//存放最短路径长度
bool vis[maxn];//是否访问过
vector<int> pre[maxn];//存放顶点在最短路径中的前驱

void DJS(int s)
{
    fill(d, d + n, INT_MAX);
    d[s] = 0;

    for (int i = 0; i < n; i++)
    {   
        int u = -1, min = INT_MAX;

        for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
            if (!vis[i] && d[i] < min)  min = d[u = i];

        if (u == -1) return;//如果剩下的顶点与源点不通，返回

        vis[u] = true;

        for (int v = 0; v < n; v++)
        {
            if (vis[v] || G[u][v] == INT_MAX) continue;

            int t = d[u] + G[u][v];

            if (t < d[v])
            {
                d[v] = t;
                pre[v].clear();
                pre[v].push_back(u);
            }  
            else if (t == d[v])
                pre[v].push_back(u);
        }
    }
}

int opt_cost = INT_MAX;//存放最少花费
vector<int> path, temp_path;

void DFS(int v)
{
    if (v == c1)//递归边界，如果遍历到起点
    {
        temp_path.push_back(v);

        int val = 0;
        for (int i = temp_path.size() - 1; i > 0; i--)
            val += cost[temp_path[i]][temp_path[i - 1]];

        if (val < opt_cost) 
        {
            opt_cost = val;
            path = temp_path;
        }

        temp_path.pop_back();

        return;
    }

    temp_path.push_back(v);

    for (int i = 0; i < pre[v].size(); i++)
        DFS(pre[v][i]);

    temp_path.pop_back();
}

int main(void) 
{
    scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
    fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
    while (m--)
    {
        int a, b, l, c;
        scanf("%d %d %d %d", &a, &b, &l, &c);

        G[a][b] = G[b][a] = l;
        cost[a][b] = cost[b][a] = c;
    }

    DJS(c1);
    DFS(c2);

    for (int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);

    printf("%d %d", d[c2], opt_cost);

    return 0;
}