码迷元首 @ 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)的