新年好

原题链接

题目描述

重庆城里有 \(n\) 个车站，\(m\) 条 双向 公路连接其中的某些车站。

每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 1，他有五个亲戚，分别住在车站 \(a,b,c,d,e\)。

过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。

怎样走，才需要最少的时间？

---

思路 Dijkstra + DFS

需要预处理出以 佳佳的家和所有亲戚家 为起点的单源最短路，然后以佳佳的家为起点，不同亲戚先后的顺序，DFS搜索出最小答案。

代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010;
const int inf = 0x3f3f3f3f;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int source[6];
int dist[6][N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(int start, int dist[]) {
    memset(dist, 0x3f, N * 4);
    memset(st, false, sizeof st);
    dist[start] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, start});

    while (!q.empty()) {
        auto [distence, ver] = q.top();
        q.pop();

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distence + w[i]) {
                dist[j] = distence + w[i];
                q.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distence) {
    if (u == 6) return distence;

    int res = inf;
    for (int i = 1; i <= 5; i++) {
        if (!st[i]) {
            st[i] = true;
            int next = source[i];
            res = min(res, dfs(u + 1, i, dist[start][next] + distence));
            st[i] = false;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    for (int i = 1; i <= 5; i++) cin >> source[i];
    source[0] = 1;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    for (int i = 0; i <= 5; i++) dijkstra(source[i], dist[i]);

    memset(st, false, sizeof st);
    cout << dfs(1, 0, 0) << endl;

    return 0;
}