当前位置:网站首页>Dijkstr heap optimization
Dijkstr heap optimization
2022-08-06 08:55:00 【ThXe】
typedef pair<int, int> PII;
const int N = 1e6 + 10;
struct DIJKSTRA {
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void init() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(int s,int end)
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({
0, s });
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({
dist[j], j });
}
}
}
if (dist[end] == 0x3f3f3f3f) return -1;
return dist[end];
}
void output() {
cout << dijkstra(1, n) << endl;
}
}Dij;//mlogn
边栏推荐
- From "prairie cattle" to "digital cattle": Mengniu's digital transformation!
- SPFA模板
- Linux - several ways to install MySQL
- The web version of Xshell supports FTP connection and SFTP connection
- Two important self-learning functions in pytorch dir(); help()
- Web端查看Liunx日志,网页端查看Liunx日志
- rain cloud animation
- Test case design method - detailed explanation of scenario method
- Parameter ‘courseId’ not found. Available parameters are [arg1, arg0, param1, para
- Free and open source web version of Xshell [Happy New Year to everyone]
猜你喜欢
随机推荐
免费的开源的 网页版Xshell【同祝贺大家新年快乐】
Linux——MySQL安装的几种方式
Card hovering frosted glass effect
记 es6 Set去重实现常用菜单
Experiment 9 (Exchange Comprehensive Experiment)
5. 自动引入打包资源 plugins的使用
韩流体小球加载动画
The 22nd day of the special assault version of the sword offer
HCIP 18 days notes
LinkedList 是如何完成添加的?
LeetCode - 1047. Remove all adjacent duplicates in a string
yum offline installation
QT配置,缺失.dll
LeetCode - 345. The reversal in the string vowels
MySQL的基本操作--创建数据库及删除数据库
Web端查看Liunx日志,网页端查看Liunx日志
微服务下token设计方案
软件测试八款优秀的API安全测试工具,会用三款工作效率能提升50%
errorCode 1045, state 28000错误详解即解决方法
卡片懸停毛玻璃效果









