新年好

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1989 字
六个关键点Dijkstra后枚举拜访顺序
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1500
// 题意：从 1 号车站出发去拜访 5 个指定亲戚所在车站，顺序任意，求走完这 5 站的最少总时间。
// 思路：对 1 号站和 5 个亲戚站共 6 个关键点各跑一次 Dijkstra，得到它们之间的两两最短路，再枚举 5! 种拜访顺序取最小总和。
// 复杂度：O(6*M log N + 5!) 时间 / O(N+M) 空间
// 易错点：Dijkstra 的源点是 6 个而不是 5 个，别漏掉起点 1 号站；距离累加可能超过 int，要用 long long。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
const long long INF = (1LL << 60);
struct Edge{
    int to, w;
};
vector<Edge> adj[MAXN];
long long dista[6][MAXN];
long long dd[6][6];
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<int> key(6);
    key[0] = 1;
    for(int i = 1; i <= 5; i++) cin >> key[i];
    for(int i = 0; i < m; i++){
        int x, y, t;
        cin >> x >> y >> t;
        adj[x].push_back({y, t});
        adj[y].push_back({x, t});
    }
    for(int s = 0; s < 6; s++){
        for(int i = 1; i <= n; i++) dista[s][i] = INF;
        dista[s][key[s]] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push({0, key[s]});
        while(!pq.empty()){
            long long du = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if(du != dista[s][u]) continue;
            for(size_t i = 0; i < adj[u].size(); i++){
                int v = adj[u][i].to;
                long long nd = du + adj[u][i].w;
                if(nd < dista[s][v]){
                    dista[s][v] = nd;
                    pq.push({nd, v});
                }
            }
        }
    }
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++) dd[i][j] = dista[i][key[j]];
    }
    vector<int> ord;
    for(int i = 1; i <= 5; i++) ord.push_back(i);
    long long ans = INF;
    sort(ord.begin(), ord.end());
    do{
        long long cur = dd[0][ord[0]];
        for(int i = 1; i < 5; i++) cur += dd[ord[i - 1]][ord[i]];
        if(cur < ans) ans = cur;
    }while(next_permutation(ord.begin(), ord.end()));
    cout << ans << '\n';
    return 0;
}
新年好

正文

一本通·提高篇的其它内容
