我的代码和题解中的一样是Dij,为什么我只有10pts,其他点WA?
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
#define m_p make_pair
#define INF 2147483647
#define INFL 9223372036854775807LL
struct edge {
int v, w;
};
vector<edge> g[5010];
set<pii> h;
int d1[5010], d2[5010];
int main() {
int n, r;
cin >> n >> r;
for (int i = 1; i <= n; i++) d1[i] = d2[i] = INF;
while (r--) {
int a, b, d;
cin >> a >> b >> d;
g[a].push_back((edge) {b, d});
}
h.insert(pii(0, 1));
d1[1] = 0;
while (!h.empty()) {
int d = h.begin() -> first;
int u = h.begin() -> second;
h.erase(h.begin());
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
int w = g[u][i].w;
if (d1[v] > d + w) {
h.erase(pii(d1[v], v));
d2[v] = d1[v];
d1[v] = d + w;
h.insert(pii(d1[v], v));
} else if (d2[v] > d + w) {
h.erase(pii(d2[v], v));
d2[v] = d + w;
h.insert(pii(d2[v], v));
}
}
}
cout << d2[n];
return 0;
}