AcWing 1135. 新年好

题目传送门

#include 
using namespace std;

typedef pair PII;

const int N = 50010;  //车站数目
const int M = 200010; //公路数目
const int INF = 0x3f3f3f3f;

int n, m; //车站数目,公路数目

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

int dist[6][N]; //到每个亲戚家的最短距离
int source[6];  //亲戚家，0号索引：佳佳的家在车站1，他有五个亲戚
bool st[N];     // Dijkstra堆优化版本专用,是否在队列中

// start:出发点
// dist[]:是全局变量dist[6][N]的某一个二维，其实是一个一维数组
// C++的特点，如果数组做参数传递的话,将直接修改原地址的数据
void dijkstra(int start, int dist[]) {
    dist[start] = 0;
    memset(st, 0, sizeof st);

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

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (!st[u]) {
            st[u] = true;
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[u] + w[i]) {
                    dist[j] = dist[u] + w[i];
                    q.push({dist[j], j});
                }
            }
        }
    }
}

int ans = INF;
// step:走的步数
// pre:前序结点
// sum:按此路径走的总距离和
// 返回值：从佳佳家出发，走完所有亲戚家，枚举所有全排列组合中找到的最小距离和
void dfs(int step, int pre, int sum) {
    //如果完成全排列，那么返回最短的距离和
    if (step == 5 + 1) {
        ans = min(ans, sum);
        return;
    }
    //预求最小先设最大
    //五个亲戚家
    for (int i = 1; i <= 5; i++)
        if (!st[i]) {          //如果这个亲戚没走过
            int u = source[i]; //根据第几个亲戚，找出这家亲戚的节点号
            st[i] = true;      //走他
            dfs(step + 1, i, sum + dist[pre][u]);
            st[i] = false; //回溯
        }
}

int main() {
    cin >> n >> m;
    source[0] = 1;                                 // 1号车站是佳佳家,索引是0
    for (int i = 1; i <= 5; i++) cin >> source[i]; //五个亲戚家
    memset(h, -1, sizeof h);                       //初始化链表头
    // m条边
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    //计算从任意一点出发，到达其它几个点的最短路径
    //第一个参数是出发点，第二个参数是个二维数组，描述到其它任意一个点的距离
    memset(dist, 0x3f, sizeof dist); //将二维数组全部实始化为INF
    for (int i = 0; i < 6; i++) dijkstra(source[i], dist[i]);

    // dfs还要用这个st数组做其它用途，所以，需要再次的清空
    memset(st, 0, sizeof st);
    // 1：准备走第一家亲戚，0：前序是佳佳自己家，0：已经走过的距离和是0
    dfs(1, 0, 0);
    printf("%d\n", ans);
    return 0;
}