新年好

固定点经过最短路 T3

题目描述

原题来自：CQOI 2005

重庆城里有 $n$ 个车站，$m$ 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$，他有五个亲戚，分别住在车站 $a,b,c,d,e$。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

输入格式

第一行：$n,m$ 为车站数目和公路的数目。

第二行：$a,b,c,d,e$ 为五个亲戚所在车站编号。

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

输出格式

输出仅一行，包含一个整数 $T$，为最少的总时间。

样例

输入

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\le n\le 50000,1\le m\le 10^5,1<a,b,c,d,e\le n,1\le x,y\le n,1\le t\le 100$。

思路

以每一个车站为起点, 求一次全图最短路, 包括家在的地方0。 求完之后dfs遍历所有车站经过排列, 然后依次计算最短路求和即可。

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
 
int readInt()
{
    int t;
    cin >> t;
    return t;
}
 
#define debug
//------- Coding Area ---------//
const int N = 5e4 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
long long dist[6][N];
bool st[N];
int source[6];
int n, m;
 
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
 
void spfa(int start, long long dist[])
{
    memset(dist, 0x3f, N * 8);
    static int q[N];
    int hh = 0, tt = 1;
    q[0] = start;
    dist[start] = 0;
    while (hh != tt)
    {
        int t = q[hh++];
        if (hh == N)
            hh = 0;
        st[t] = false;
 
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt++] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
 
long long dfs(int u, int s, long long d)
{
    if (u == 6)
        return d;
 
    long long res = INF;
    for (int i = 1; i < 6; i++)
    {
        if (st[i])
            continue;
        int next = source[i];
        st[i] = true;
        res = min(res, dfs(u + 1, i, dist[s][next] + d));
        st[i] = false;
    }
 
    return res;
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
 
    source[0] = 1;
    REP(i, 1, 6)
    cin >> source[i];
 
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
 
    for (int i = 0; i < 6; i++)
        spfa(source[i], dist[i]);
    // cout << dfs(1, 0, 0);
    int tmp[] = {0, 1, 2, 3, 4, 5}, cnt = 0, tot = 0, res = INF;
    while (1)
    {
        if (cnt == 120)
            break;
        cnt++;
        tot = dist[0][source[tmp[1]]];
        for (register int i = 1; i <= 4; i++)
            tot += dist[tmp[i]][source[tmp[i + 1]]];
        res = min(res, tot);
        next_permutation(tmp + 1, tmp + 6);
    }
    cout << res << endl;
 
    return 0;
}