@[Houjiadong](/user/1157431) 1.数组开太小了,因为有5e5条边,2.初始值要设为$2^{31}-1$,因为不合法要输出这个
by __zaa__ @ 2024-03-14 16:28:39
@[__zaa__](/user/716965) 谢谢佬 但是为啥子我的第三个测试点还是WA捏
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e5+10;
int n, m,s;
int h[N], w[N + 10], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra() {
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 });
}
}
}
}
int main() {
cin >> n >> m >> s;
memset(h, -1, sizeof(h));
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
for (int i = 1;i <= n;i++) {
if(dist[i]!=0x3f3f3f3f)cout << dist[i] << " ";
else { cout << 2e31 - 1; }
}
}
```
by Houjiadong @ 2024-03-14 16:36:25
@[Houjiadong](/user/1157431) ```else { cout << 2e31 - 1; }```没输出空格
by __zaa__ @ 2024-03-14 16:37:39
而且是(1<<31)-1.
by __zaa__ @ 2024-03-14 16:38:09
@[__zaa__](/user/716965) hh感谢~~
by Houjiadong @ 2024-03-14 16:43:22