用map实现的邻接矩阵,二叉堆优化,求助

P4779 【模板】单源最短路径(标准版)

码迷元首 @ 2022-09-17 23:11:45

#include<bits/stdc++.h>
#define inf 1000000001

struct side
{
    int to;
    int w;
    bool operator <(side b) const
    {
        return w < b.w;
    }
};
struct path
{
    int u,v;
    bool operator<(path b)const
    {
        return u+v<b.u+b.v;
    }
};
int n, m, s;
int dis[100001];
std::priority_queue<side> h;
std::map<path,int> graph;
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[path{u,v}] = w;
    }
    for (int i = 1; i <= n; i++)
        dis[i] = inf;

    dis[s] = 0;
    h.push(side{s, 0});
    while (!h.empty())
    {
        side tmp = h.top();
        h.pop();
        int x = tmp.to;
        if (dis[x] != tmp.w)continue;
        for (int i = 1; i <= n; i++)
        {
            if (graph.count(path{x,i})==0)continue;

            int y = i, w =graph[path{x,i}];
            if (dis[y] > dis[x] + w)
            {
                dis[y] = dis[x] + w;
                h.push(side{y, dis[y]});
            }
        }
    }
    for (int i = 1; i <= n; i++)printf("%d ", dis[i]);

}

by 码迷元首 @ 2022-09-17 23:23:19

还有就是map的count方法用于判断关键字是否存在时,它以其线性时间复杂度闻(gou)名(shi)于(la)世(ji),有无方法优化?求助各路大仙orz


by HeCao2008 @ 2022-09-17 23:30:29

领接矩阵会炸把


by _•́へ•́╬_ @ 2022-09-18 00:00:59

@码迷元首 谁跟你说count是线性复杂度的


by 码迷元首 @ 2022-09-18 07:16:48

@•́へ•́╬ count的意义是统计个数,这还不得从头到尾搜一遍吗。我在百度上看到的


by 码迷元首 @ 2022-09-18 07:25:50

@码迷元首 好像只有c++20才有O(lg n)的contains方法


by _•́へ•́╬_ @ 2022-09-18 10:48:04

@码迷元首 map不可重,在平衡树上找那一个节点,显然是O(lg)的


|