10 / 30 分,主要就是程序中标的 for 循环出错了
萌新求助 /kel/dk 求大佬帮忙
#include <bits/stdc++.h>
using namespace std;
struct node {
int val, next, length;
} e1[50086], e2[50086], e3[50086];
int n, m, cnt, pnt, hnt;
int dist1[50086], sum1[50086], head1[50086];
int dist2[50086], sum2[50086], head2[50086];
int dist3[50086], sum3[50086], head3[50086];
const int inf = 0x3f3f3f3f;
void AddEdge01 (int u, int v, int w) {
e1[cnt].val = v;
e1[cnt].next = head1[u];
e1[cnt].length = w;
head1[u] = cnt;
cnt--;
}
void AddEdge02 (int u, int v, int w) {
e2[pnt].val = v;
e2[pnt].next = head2[u];
e2[pnt].length = w;
head2[u] = pnt;
pnt--;
}
struct cmp01 {
bool operator () (int a, int b) {
return dist1[a] > dist1[b];
}
};
struct cmp02 {
bool operator () (int a, int b) {
return dist2[a] > dist2[b];
}
};
void SPFA01 () {
int s = n;
priority_queue <int, vector<int>, cmp01> q1;
for (int i = 1; i <= n; i++)
dist1[i] = inf;
dist1[s] = 0;
sum1[s] = 1;
q1.push(s);
while (!q1.empty()) {
int cur = q1.top();
q1.pop();
sum1[cur] = 0;
for (int p = head1[cur]; p > 0; p = e1[p].next)
if (dist1[e1[p].val] > dist1[cur] + e1[p].length) {
dist1[e1[p].val] = dist1[cur] + e1[p].length;
if (!sum1[e1[p].val]) {
q1.push(e1[p].val);
sum1[e1[p].val] = 1;
}
}
}
}
void SPFA02 () {
int s = n;
priority_queue <int, vector<int>, cmp02> q2;
for (int i = 1; i <= n; i++)
dist2[i] = inf;
dist2[s] = 0;
sum2[s] = 1;
q2.push(s);
while (!q2.empty()) {
int cur = q2.top();
q2.pop();
sum2[cur] = 0;
for (int p = head2[cur]; p > 0; p = e2[p].next)
if (dist2[e2[p].val] > dist2[cur] + e2[p].length) {
dist2[e2[p].val] = dist2[cur] + e2[p].length;
if (!sum2[e2[p].val]) {
q2.push(e2[p].val);
sum2[e2[p].val] = 1;
}
}
}
}
void AddEdge03 (int u, int v, int w) {
e3[++hnt].val = v;
e3[hnt].next = head3[u];
e3[hnt].length = w;
head3[u] = hnt;
}
void SPFA03 () {
int s = 1;
priority_queue <int, vector<int>, cmp02> q3;
for (int i = 1; i <= n; i++)
dist3[i] = inf;
dist3[s] = 0;
sum3[s] = 1;
q3.push(s);
while (!q3.empty()) {
int cur = q3.top();
q3.pop();
sum3[cur] = 0;
for (int p = head3[cur]; p > 0; p = e3[p].next)
if (dist3[e3[p].val] > dist3[cur] + e3[p].length) {
dist3[e3[p].val] = dist3[cur] + e3[p].length;
if (!sum3[e3[p].val]) {
q3.push(e3[p].val);
sum3[e3[p].val] = 1;
}
}
}
}
int main () {
scanf("%d%d", &n, &m);
cnt = m, pnt = m;
for (int i = 1, u, v, w1, w2; i <= m; i++) {
scanf("%d%d%d%d", &u, &v, &w1, &w2);
AddEdge01(v, u, w1);
AddEdge02(v, u, w2);
AddEdge03(u, v, 0);
}
SPFA01(), SPFA02();
// Part 1 complete : Slowest Time - 47 ms
for (int i = 1; i <= m; i++) { // 这个 for 循环出错
if (dist1[e3[i].next] - dist1[e3[i].val] != e3[i].length)
e3[i].length++;
if (dist2[e3[i].next] - dist2[e3[i].val] != e3[i].length)
e3[i].length++;
}
SPFA03();
printf("%d", dist3[n]);
// Part 2 not complete
return 0;
}