如题,样例通过情况为 11/12,n == 50000, m == 54997 时 TLE 了。有没有巨巨知道这是为何???
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010, M = 2 * N;
int e[M], ne[M], idx, h[N], w[M];
int n, m;
int d[N];
int siz;
PII hp[N];
void init() {
memset(h, -1, sizeof h);
}
void add(int a, int b, int z) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = z;
h[a] = idx++;
}
void down(int u) {
int t = u;
if (2 * u <= siz && hp[2 * u].first < hp[t].first) t = 2 * u;
if (2 * u + 1 <= siz && hp[2 * u + 1].first < hp[t].first) t = 2 * u + 1;
if (t != u) {
swap(hp[t], hp[u]);
down(t);
}
}
void up(int u) {
while (u / 2 && hp[u / 2].first > hp[u].first) {
swap(hp[u / 2], hp[u]);
u /= 2;
}
}
int dijkstra() {
memset(d, 0x3f, sizeof d);
d[1] = 0;
hp[1] = {0, 1};
siz = 1;
while (siz) {
PII t = hp[1];
hp[1] = hp[siz--];
down(1);
int now = t.second, distance = t.first;
for (int i = h[now]; ~i; i = ne[i]) {
int next = e[i];
if (d[next] > d[now] + w[i]) {
d[next] = d[now] + w[i];
hp[++siz] = {d[next], next};
up(siz);
}
}
}
if (d[n] == 0x3f3f3f3f) return -1;
else return d[n];
}
int main()
{
init();
scanf("%d%d", &n, &m);
int x, y, z;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
int ans = dijkstra();
if (ans != -1) printf("%d\n", ans);
else puts("-1");
}