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

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

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

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

你能帮他找到怎样走才需要最少的时间吗?

输入格式

第一行:包含两个整数 nm,分别表示车站数目和公路数目。

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

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

输出格式

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

数据范围

  • 1 ≤ n ≤ 50000
  • 1 ≤ m ≤ 105
  • 1 < a, b, c, d, en
  • 1 ≤ x, yn
  • 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

代码实现

#include <iostream>
#include <cstring>
#include <bitset>
#include <unordered_map>
#include <queue>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;
using LL = long long;
const int N = 1e6;

int p[5], n, m, h[N], e[N], w[N], ne[N], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
LL getIdx(int i, int j) {
    return i * N + j;
}
int dijkstra(int s, int en) {
    int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    bitset <N> st;
    priority_queue <PII, vector <PII>, greater <PII>> heap;
    heap.push({0,s});
    while(heap.size()) {
        auto t = heap.top(); heap.pop();
        if (st[t.y]) continue;
        st[t.y] = 1;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i]) {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    return dist[en];
}
int id = 0;
vector <vector <int>> Sequences;
bitset <5> st;
void dfs(vector <int> Sequence, int id) {
    if (id == 5) {
        Sequences.push_back(Sequence);
        return ;
    }
    for (int i = 0; i < 5; ++i) {
        if (!st[i]) {
            st[i] = 1;
            Sequence[id] = p[i];
            dfs(Sequence, id + 1);
            st[i] = 0;
        }
    }

}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < 5; ++i) cin >> p[i];
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    unordered_map <LL,int> hashtable;
    for (int i = 0; i < 5; ++i) hashtable[getIdx(1,p[i])] = hashtable[getIdx(p[i],1)] = dijkstra(1,p[i]);
    for (int i = 0; i < 5; ++i)
        for (int j = i + 1; j < 5; ++j)
            hashtable[getIdx(p[i],p[j])] = hashtable[getIdx(p[j],p[i])] = dijkstra(p[i],p[j]);
    vector <int> Sequence(5);
    dfs(Sequence,0);
    int res = 0x7fffffff;
    for (auto& Sequence : Sequences) {
        int ans = 0;
        for (int i = 0; i < 5; ++i) {
            if (!i) ans += hashtable[getIdx(1,Sequence[i])];
            else ans += hashtable[getIdx(Sequence[i - 1],Sequence[i])];
        }
        res = min(res, ans);
    }
    cout << res;
    return 0;
} 
分类: Dijkstra

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status