AcWing 1135. 新年好 图论 枚举

地址  https://www.acwing.com/problem/content/description/1137/

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

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

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

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

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

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

输入格式
第一行：包含两个整数 n,m，分别表示车站数目和公路数目。

第二行：包含五个整数 a,b,c,d,e，分别表示五个亲戚所在车站编号。

以下 m 行，每行三个整数 x,y,t，表示公路连接的两个车站编号和时间。

输出格式
输出仅一行，包含一个整数 T，表示最少的总时间。

数据范围
1≤n≤50000,
1≤m≤105,
1<a,b,c,d,e≤n,
1≤x,y≤n,
1≤t≤100
输入样例：
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
输出样例：
21

算法1
使用DFS枚举各种路径的组合可能 然后使用最短路计算各点之间的最短距离。
可优化的点在于 先计算最短路径后，在枚举路径计算最短路径可以直接查表。
但是数据居然卡SPFA ，再次尝试 使用堆优化的dijkstra

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

/*
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
*/

const int N = 50010;
const int M = 1e5 + 10;

typedef pair<int, int> PII;

vector < pair<int, int>> g[N];
int dist[N];
bool st[N];
int n, m;

int ans = 3e8;
int family[7];
int familyCopy[7];
int path[7];
int allDist[7][N];

int spfa(int p)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));

    //p点作为起始 到其他点的最短距离
    dist[p] = 0;
    queue<int> q;
    q.push(p);
    st[p] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;

            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int  dfs(int count)
{
    if (count == 6) {
        int sum = 0;
        for (int i = 0; i < 5; i++) {
            int from = path[i];
            int to = path[i + 1];
            int idx = -1;
            for (int j = 0; j < 6; j++) {
                if (from == familyCopy[j]){
                    idx = j; break;
                }
            }
            sum += allDist[idx][to];
        }
        return sum;
    }

    for (int i = 1; i <= 5; i++) {
        if (family[i] != 0) {
            path[count] = family[i];family[i] = 0;count++;
            ans =  min (ans,dfs(count));
            count--;family[i] = path[count];path[count] = 0;
        }
    }


    return ans; 
}

int dij(int p)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[p] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({ 0, p });

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

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

        for (int i = 0; i < g[ver].size(); i++) {
            int j = g[ver][i].first;
            int w = g[ver][i].second;

            if (dist[j] > dist[ver] + w) {
                dist[j] = dist[ver] + w;
                heap.push({ dist[j],j });
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;

    return dist[n];
}

void useDIJ() {
    for (int i = 0; i < 6; i++) {
        dij(family[i]);
        memcpy(allDist[i], dist, sizeof(dist));
    }

    path[0] = 1;
    cout << dfs(1) << endl;
}


void useSPFA() {
    for (int i = 0; i < 6; i++) {
        spfa(family[i]);
        memcpy(allDist[i], dist, sizeof(dist));
    }

    path[0] = 1;
    cout << dfs(1) << endl;
}

int main()
{
    cin >> n >> m;
    family[0] = 1;
    for (int i = 1; i <= 5; i++) {
        cin >> family[i];
    }
    memcpy(familyCopy, family, sizeof(family));

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({ b,c });
        g[b].push_back({ a,c });
    }

    useDIJ();
    //useSPFA();



    return 0;
}