#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5e4 + 10;
const long long inf = 1e15;
bool del[maxm];
int l[maxm], r[maxm], w[maxm], c[maxm];
int n, m;
vector <int> g[maxn];
bool imp[maxm];
vector <long long> shortest_path(int src, bool rev = false, bool mark = false) {
vector <long long> d (n, inf);
vector <bool> done (n, false);
d[src] = 0;
while(true) {
int x = -1;
for(int i = 0; i < n; i++) {
if(done[i]) continue;
if(x == -1 || d[x] > d[i]) {
x = i;
}
}
if(x == -1) break;
done[x] = true;
for(int e : g[x]) {
if(del[e]) continue;
if(rev && l[e] == x) continue;
if(!rev && r[e] == x) continue;
int y = l[e] ^ r[e] ^ x;
if(d[y] > d[x] + w[e]) {
d[y] = d[x] + w[e];
}
}
}
if(mark) {
vector <int> par (n, -1);
for(int x = 0; x < n; x++) {
for(int e : g[x]) {
if(del[e]) continue;
if(rev && l[e] == x) continue;
if(!rev && r[e] == x) continue;
int y = l[e] ^ r[e] ^ x;
if(d[y] == d[x] + w[e]) {
par[y] = e;
}
}
}
for(int i = 0; i < n; i++) if(par[i] != -1) imp[par[i]] = true;
}
return d;
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> l[i] >> r[i] >> w[i] >> c[i];
l[i] -= 1;
r[i] -= 1;
g[l[i]].push_back(i);
g[r[i]].push_back(i);
}
vector <long long> srcPath (m, inf), desPath(m, inf);
vector <long long> leftSrc (m, inf), srcRight (m, inf);
vector <long long> leftDes (m, inf), desRight (m, inf);
fill(imp, imp + m, false);
auto fromSrc = shortest_path(0, false, true);
for(int i = 0; i < m; i++) {
if(imp[i]) {
del[i] = true;
auto u = shortest_path(0);
srcPath[i] = u[n - 1];
srcRight[i] = u[r[i]];
del[i] = false;
} else {
srcPath[i] = fromSrc[n - 1];
srcRight[i] = fromSrc[r[i]];
}
}
fill(imp, imp + m, false);
auto fromDes = shortest_path(n - 1, false, true);
for(int i = 0; i < m; i++) {
if(imp[i]) {
del[i] = true;
auto v = shortest_path(n - 1);
desRight[i] = v[r[i]];
desPath[i] = v[0];
del[i] = false;
} else {
desRight[i] = fromDes[r[i]];
desPath[i] = fromDes[0];
}
}
fill(imp, imp + m, false);
auto toSrc = shortest_path(0, true, true);
for(int i = 0; i < m; i++) {
if(imp[i]) {
del[i] = true;
auto u = shortest_path(0, true);
leftSrc[i] = u[l[i]];
del[i] = false;
} else {
leftSrc[i] = toSrc[l[i]];
}
}
fill(imp, imp + m, false);
auto toDes = shortest_path(n - 1, true, true);
for(int i = 0; i < m; i++) {
if(imp[i]) {
del[i] = true;
auto v = shortest_path(n - 1, true);
leftDes[i] = v[l[i]];
del[i] = false;
} else {
leftDes[i] = toDes[l[i]];
}
}
long long ans = fromSrc[n - 1] + fromDes[0];
for(int i = 0; i < m; i++) {
long long res = c[i];
res += min(srcRight[i] + w[i] + leftDes[i], srcPath[i]);
res += min(desRight[i] + w[i] + leftSrc[i], desPath[i]);
ans = min(ans, res);
}
if(ans >= inf) ans = -1;
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
384 KB |
Output is correct |
2 |
Correct |
57 ms |
384 KB |
Output is correct |
3 |
Correct |
93 ms |
504 KB |
Output is correct |
4 |
Correct |
92 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
19 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
95 ms |
504 KB |
Output is correct |
11 |
Correct |
92 ms |
384 KB |
Output is correct |
12 |
Correct |
93 ms |
504 KB |
Output is correct |
13 |
Correct |
43 ms |
512 KB |
Output is correct |
14 |
Correct |
73 ms |
504 KB |
Output is correct |
15 |
Correct |
69 ms |
504 KB |
Output is correct |
16 |
Correct |
68 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
682 ms |
4600 KB |
Output is correct |
2 |
Correct |
672 ms |
4856 KB |
Output is correct |
3 |
Correct |
698 ms |
4728 KB |
Output is correct |
4 |
Correct |
98 ms |
512 KB |
Output is correct |
5 |
Correct |
80 ms |
504 KB |
Output is correct |
6 |
Correct |
28 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
373 ms |
4856 KB |
Output is correct |
10 |
Correct |
376 ms |
4856 KB |
Output is correct |
11 |
Correct |
548 ms |
4744 KB |
Output is correct |
12 |
Correct |
547 ms |
4728 KB |
Output is correct |
13 |
Correct |
555 ms |
4856 KB |
Output is correct |
14 |
Correct |
538 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
504 KB |
Output is correct |
2 |
Correct |
57 ms |
384 KB |
Output is correct |
3 |
Correct |
664 ms |
3704 KB |
Output is correct |
4 |
Correct |
60 ms |
384 KB |
Output is correct |
5 |
Correct |
866 ms |
4760 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
766 ms |
5368 KB |
Output is correct |
9 |
Correct |
759 ms |
5112 KB |
Output is correct |
10 |
Incorrect |
899 ms |
5456 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
384 KB |
Output is correct |
2 |
Correct |
57 ms |
384 KB |
Output is correct |
3 |
Correct |
93 ms |
504 KB |
Output is correct |
4 |
Correct |
92 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
19 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
95 ms |
504 KB |
Output is correct |
11 |
Correct |
92 ms |
384 KB |
Output is correct |
12 |
Correct |
93 ms |
504 KB |
Output is correct |
13 |
Correct |
43 ms |
512 KB |
Output is correct |
14 |
Correct |
73 ms |
504 KB |
Output is correct |
15 |
Correct |
69 ms |
504 KB |
Output is correct |
16 |
Correct |
68 ms |
512 KB |
Output is correct |
17 |
Correct |
682 ms |
4600 KB |
Output is correct |
18 |
Correct |
672 ms |
4856 KB |
Output is correct |
19 |
Correct |
698 ms |
4728 KB |
Output is correct |
20 |
Correct |
98 ms |
512 KB |
Output is correct |
21 |
Correct |
80 ms |
504 KB |
Output is correct |
22 |
Correct |
28 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
373 ms |
4856 KB |
Output is correct |
26 |
Correct |
376 ms |
4856 KB |
Output is correct |
27 |
Correct |
548 ms |
4744 KB |
Output is correct |
28 |
Correct |
547 ms |
4728 KB |
Output is correct |
29 |
Correct |
555 ms |
4856 KB |
Output is correct |
30 |
Correct |
538 ms |
4984 KB |
Output is correct |
31 |
Correct |
94 ms |
504 KB |
Output is correct |
32 |
Correct |
57 ms |
384 KB |
Output is correct |
33 |
Correct |
664 ms |
3704 KB |
Output is correct |
34 |
Correct |
60 ms |
384 KB |
Output is correct |
35 |
Correct |
866 ms |
4760 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
766 ms |
5368 KB |
Output is correct |
39 |
Correct |
759 ms |
5112 KB |
Output is correct |
40 |
Incorrect |
899 ms |
5456 KB |
Output isn't correct |
41 |
Halted |
0 ms |
0 KB |
- |