历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1135. 【算法提高课】新年好（Dijkstra）原题链接简单

作者：

incra , 2022-12-21 07:29:15 , 所有人可见 , 阅读 2612

<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$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$

输入样例：

输出样例：

思路

由于拜访亲戚的顺序不确定，所以我们考虑变化访问顺序，这里我们可以用$\text{next_permutation}$函数来求出下一个排列。
但是我们并不知道任意两点的距离，所以我们要分别从每一个点往所有点搜出到这个点最短路，这里我选用了堆优化的$\text{Dijkstra}$
注意我的代码里的数组$d$的第一维并不是某一个点，而是这个点是题目中给出点中的第几个亲戚的位置。

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair <int,int> PII;
const int N = 50010,M = 200010,K = 10,INF = 0x3f3f3f3f;
int n,m;
int id[K];
int d[K][N];
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++;
}
void dijkstra (int s,int dist[]) {
    bool st[N] = {false};
    dist[s] = 0;
    priority_queue <PII,vector <PII>,greater <PII>> heap;
    heap.push ({0,s});
    while (!heap.empty ()) {
        int t = heap.top ().second;
        heap.pop ();
        if (st[t]) continue;
        st[t] = true;
        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];
                heap.push ({dist[j],j});
            }
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    memset (d,0x3f,sizeof (d));
    cin >> n >> m;
    id[1] = 1;
    for (int i = 2;i <= 6;i++) cin >> id[i];
    while (m--) {
        int a,b,c;
        cin >> a >> b >> c;
        add (a,b,c),add (b,a,c);
    }
    for (int i = 1;i <= 6;i++) dijkstra (id[i],d[i]);
    int a[K];
    for (int i = 1;i <= 6;i++) a[i] = i;
    int ans = INF;
    do {
        int res = d[a[1]][id[a[2]]];
        for (int i = 2;i <= 5;i++) res += d[a[i]][id[a[i + 1]]];
        ans = min (ans,res);
    }
    while (next_permutation (a + 2,a + 7));
    cout << ans << endl;
    return 0;
}

14 评论

一只学术蜗牛 2023-08-21 20:59

我可以秀一下吗？我的全STL版比博主的快了近300ms

Soel 2023-08-21 21:14

我看了下用了std::unordered_map…卡掉哈希的话寻找元素的时间复杂度就不是O1了
原理是很容易找到stl自带的base

Soel 2023-08-21 21:25

std::unordered_map 在acm赛制下可能会比较吃亏的，注意一下

Soel 2023-08-16 16:16

贴一个SLF的优化:

#include<bits/stdc++.h>

using i64 = long long;
const int N = 2e5 + 10,INF = 0x3f3f3f3f;
const int M = 2 * N;
int n, m;
int source[6];
int h[N], e[M], ne[M], w[M], idx;
std::deque<int> q;
int dist[6][N];
bool st[N];
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, int dist[]) {
    std::memset(dist, 0x3f, N * 4);
    std::memset(st,false,sizeof st);
    dist[start] = 0;
    q.push_back(start);
    while (q.size()) {
        auto t = q.front(); q.pop_front();
        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]) {
                    if(q.size() and dist[j]>dist[q.front()]) q.push_back(j);
                    else q.push_front(j);
                    st[j] = true;
                }
            }
        }
    }
}
int dfs(int u, int start, int distance) {
    if (u == 6) return distance;
    int res = INF;
    for (int i = 1; i <= 5; ++i) {
        if (!st[i]) {
            int next = source[i];
            st[i] = true;
            res = std::min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = false;
        }
    }
    return res;
}
auto main() -> signed {

    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(2);
    std::fill(h, h + N, -1);
    std::cin >> n >> m;
    source[0] = 1;
    for (int i = 1; i <= 5; ++i) std::cin >> source[i];
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < 6; ++i) spfa(source[i], dist[i]);
    //for (int i=1;i<2*m;++i) std::cout<<w[i]<<" \n"[i==2*m-1];
    std::cout << dfs(1, 0, 0) << '\n';

    return 0;
}