@[xu_zhihao](/user/1063855)
1. 建议改一下马蜂
2. 你的vis数组呢?
我并不知道你的写法需不需要vis数组,但是建议加上。
by litjohn @ 2024-04-04 17:17:06
@[litjohn](/user/537934) 似乎
```cpp
for(int i=0;i<=100000;i++)
{
d[i]=inf;
}
```
这个就是
by xu_zhihao @ 2024-04-04 17:18:39
@[xu_zhihao](/user/1063855)
热知识:你并不需要在优先队列里存`pair<int,int>`,你只需要换一个`cmp`:
```cpp
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,cmp>q;
```
by litjohn @ 2024-04-04 17:19:50
@[xu_zhihao](/user/1063855)
你这个是距离与访问兼用。
但是,在你更新某个节点的距离时,你其实并没有访问这个节点,而是正在访问它周围的某个节点。
by litjohn @ 2024-04-04 17:21:58
@[litjohn](/user/537934) 这我知道,只是懒的搞awa
by xu_zhihao @ 2024-04-04 17:27:43
@[xu_zhihao](/user/1063855) 帮你调了一下码风:
```cpp
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> e[100010];
int dis[100010], n, m;
bool vis[100010];
struct cmp {
bool operator()(int a, int b) {
return dis[a] > dis[b];
}
};
priority_queue<int, vector<int>, cmp> q;
void Dijkstra(int start) {
memset(dis, 0x7f, sizeof(dis));
dis[1] = 0;
q.emplace(start);
while (!q.empty()) {
int qaq = q.top();
q.pop();
vis[qaq] = true;
for (auto i: e[qaq]) {
if (i.second + dis[qaq] < dis[i.first]) {
dis[i.first] = dis[qaq] + i.second;
if (!vis[i.first]) {
q.emplace(i.first);
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
e[a].emplace_back(b, w);
e[b].emplace_back(a, w);
}
Dijkstra(1);/*
for (int i = 1; i <= n; ++i) {
cout<<dis[i]<<" ";
}*/
if (dis[n] >= 1e9) {
cout << -1;
} else {
cout << dis[n];
}
return 0;
}
```
by litjohn @ 2024-04-04 17:34:00
@[xu_zhihao](/user/1063855) 边权范围是什么
by fsdgakjl @ 2024-04-04 17:35:53
@[litjohn](/user/537934) 预告一下,我要开喷了
by jason_sun @ 2024-04-04 18:15:59
这是一份AC代码的记录
https://www.luogu.com.cn/record/61387486
为什么不再交一遍是因为我不想影响我的每日通过数
将其比较函数改为你上文所述,记录如下
https://www.luogu.com.cn/record/154280893
再复制第一篇题解并将代码改为你上文所述,记录如下
https://www.luogu.com.cn/record/154281801
我的评价是你家优先队列可以动态修改堆里数的值了
by jason_sun @ 2024-04-04 18:20:38
@[xu_zhihao](/user/1063855) 别被误导了,另外你的死因是小根堆写成大根堆了,将
`priority_queue<pair<int,int>>q;`
改为
`priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;`
即可
by jason_sun @ 2024-04-04 18:28:05