# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
705691 |
2023-03-05T01:01:12 Z |
cig32 |
Olympic Bus (JOI20_ho_t4) |
C++17 |
|
1000 ms |
7196 KB |
#include "bits/stdc++.h"
#define int long long
using namespace std;
struct edge {
int u, v, c, d;
};
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
edge e[m+1];
for(int i=1; i<=m; i++) {
cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
}
int dist1[n+1][n+1], distn[n+1][n+1];
int rev1[n+1][n+1], revn[n+1][n+1]; // b=0: nothing
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
dist1[i][j] = distn[i][j] = rev1[i][j] = revn[i][j] = 1e18;
}
dist1[i][1] = 0;
distn[i][n] = 0;
rev1[i][1] = 0;
revn[i][n] = 0;
}
for(int b=0; b<=n; b++) {
vector<pair<int, int> > adj[n+1], rev[n+1];
bool in[n+1];
queue<int> q;
for(int i=1; i<=m; i++) {
if(e[i].u != b && e[i].v != b) {
adj[e[i].u].push_back({e[i].v, e[i].c});
rev[e[i].v].push_back({e[i].u, e[i].c});
}
}
for(int i=1; i<=n; i++) in[i] = 0;
in[1] = 1;
q.push(1);
while(q.size()) {
int f = q.front();
q.pop();
in[f] = 0;
for(pair<int, int> x: adj[f]) {
if(dist1[b][x.first] > dist1[b][f] + x.second) {
dist1[b][x.first] = dist1[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
q.push(x.first);
}
}
}
}
in[n] = 1;
q.push(n);
while(q.size()) {
int f = q.front();
q.pop();
in[f] = 0;
for(pair<int, int> x: adj[f]) {
if(distn[b][x.first] > distn[b][f] + x.second) {
distn[b][x.first] = distn[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
q.push(x.first);
}
}
}
}
in[1] = 1;
q.push(1);
while(q.size()) {
int f = q.front();
q.pop();
in[f] = 0;
for(pair<int, int> x: rev[f]) {
if(rev1[b][x.first] > rev1[b][f] + x.second) {
rev1[b][x.first] = rev1[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
q.push(x.first);
}
}
}
}
in[n] = 1;
q.push(n);
while(q.size()) {
int f = q.front();
q.pop();
in[f] = 0;
for(pair<int, int> x: rev[f]) {
if(revn[b][x.first] > revn[b][f] + x.second) {
revn[b][x.first] = revn[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
q.push(x.first);
}
}
}
}
}
int ans = dist1[0][n] + distn[0][1];
vector<pair<int,int> > adj[n+1], rev[n+1];
vector<int> adj_id[n+1];
for(int i=1; i<=m; i++) {
adj_id[e[i].u].push_back(i);
adj[e[i].u].push_back({e[i].v, e[i].c});
rev[e[i].v].push_back({e[i].u, e[i].c});
}
int cnt[n+1][n+1];
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
cnt[i][j] = 0;
}
}
for(int i=1; i<=m; i++) {
cnt[e[i].u][e[i].v]++;
}
for(int i=1; i<=m; i++) {
int forward, backward;
forward = dist1[e[i].u][e[i].v] + e[i].c;
int mi = (e[i].u == n ? 0 : 1e18);
for(pair<int,int> x: adj[e[i].u]) {
mi = min(mi, x.second + revn[e[i].u][x.first]);
}
forward += mi;
forward = min(forward, dist1[e[i].u][n]);
int pt1 = (e[i].u == 1 ? 0 : 1e18);
int pt2 = (e[i].u == n ? 0 : 1e18);
for(pair<int,int> x: rev[e[i].u]) {
pt1 = min(pt1, dist1[e[i].u][x.first] + x.second);
}
int it=0;
for(pair<int,int> x: adj[e[i].u]) {
if(adj_id[e[i].u][it] == i) {
it++;
continue;
}
it++;
pt2 = min(pt2, revn[e[i].u][x.first] + x.second);
}
forward = min(forward, pt1 + pt2);
backward = distn[e[i].u][e[i].v] + e[i].c;
mi = (e[i].u == 1 ? 0 : 1e18);
for(pair<int,int> x: adj[e[i].u]) {
mi = min(mi, x.second + rev1[e[i].u][x.first]);
}
backward += mi;
backward = min(backward, distn[e[i].u][1]);
pt1 = (e[i].u == n ? 0 : 1e18);
pt2 = (e[i].u == 1 ? 0 : 1e18);
for(pair<int,int> x: rev[e[i].u]) {
pt1 = min(pt1, distn[e[i].u][x.first] + x.second);
}
it=0;
for(pair<int,int> x: adj[e[i].u]) {
if(adj_id[e[i].u][it] == i) {
it++;
continue;
}
it++;
pt2 = min(pt2, rev1[e[i].u][x.first] + x.second);
}
backward = min(backward, pt1 + pt2);
ans = min(ans, forward + backward + e[i].d);
//cout << "flip edge " << i << ": " << forward << " + " << backward << " + " << e[i].d << " = " << forward + backward + e[i].d << "\n";
}
cout << (ans <= 1e12 ? ans : -1) << "\n";
}
/*
5 6
1 2 1 10000
2 5 1 10000
5 3 1 10000
2 3 10 1
2 4 1 10000
4 1 1 10000
2 2
1 2 3 4
1 2 3 9
3 4
1 2 3 4
2 3 3 9
2 1 3 10
2 3 3 11
2 7
1 2 1 1
1 2 1 7
1 2 1 3
1 2 1 4
1 2 1 5
1 2 1 6
1 2 1 9
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
2004 KB |
Output is correct |
2 |
Correct |
6 ms |
1868 KB |
Output is correct |
3 |
Correct |
24 ms |
1944 KB |
Output is correct |
4 |
Correct |
25 ms |
1932 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
6 ms |
1876 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
48 ms |
1996 KB |
Output is correct |
11 |
Correct |
51 ms |
1920 KB |
Output is correct |
12 |
Correct |
50 ms |
1920 KB |
Output is correct |
13 |
Correct |
18 ms |
1940 KB |
Output is correct |
14 |
Correct |
23 ms |
2004 KB |
Output is correct |
15 |
Correct |
26 ms |
1928 KB |
Output is correct |
16 |
Correct |
24 ms |
1948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
696 ms |
6808 KB |
Output is correct |
2 |
Correct |
674 ms |
6704 KB |
Output is correct |
3 |
Correct |
678 ms |
6760 KB |
Output is correct |
4 |
Correct |
35 ms |
1996 KB |
Output is correct |
5 |
Correct |
18 ms |
1928 KB |
Output is correct |
6 |
Correct |
10 ms |
1876 KB |
Output is correct |
7 |
Correct |
8 ms |
1880 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
578 ms |
6708 KB |
Output is correct |
10 |
Correct |
540 ms |
6680 KB |
Output is correct |
11 |
Correct |
671 ms |
6824 KB |
Output is correct |
12 |
Correct |
620 ms |
6688 KB |
Output is correct |
13 |
Correct |
677 ms |
6804 KB |
Output is correct |
14 |
Correct |
729 ms |
7196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
2004 KB |
Output is correct |
2 |
Correct |
6 ms |
1876 KB |
Output is correct |
3 |
Correct |
412 ms |
5652 KB |
Output is correct |
4 |
Correct |
6 ms |
1876 KB |
Output is correct |
5 |
Correct |
632 ms |
6636 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
545 ms |
6656 KB |
Output is correct |
9 |
Correct |
536 ms |
6744 KB |
Output is correct |
10 |
Correct |
555 ms |
6572 KB |
Output is correct |
11 |
Correct |
583 ms |
6628 KB |
Output is correct |
12 |
Correct |
548 ms |
6876 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
566 ms |
6980 KB |
Output is correct |
20 |
Correct |
559 ms |
6768 KB |
Output is correct |
21 |
Correct |
572 ms |
6696 KB |
Output is correct |
22 |
Correct |
548 ms |
6720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
2004 KB |
Output is correct |
2 |
Correct |
6 ms |
1868 KB |
Output is correct |
3 |
Correct |
24 ms |
1944 KB |
Output is correct |
4 |
Correct |
25 ms |
1932 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
6 ms |
1876 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
48 ms |
1996 KB |
Output is correct |
11 |
Correct |
51 ms |
1920 KB |
Output is correct |
12 |
Correct |
50 ms |
1920 KB |
Output is correct |
13 |
Correct |
18 ms |
1940 KB |
Output is correct |
14 |
Correct |
23 ms |
2004 KB |
Output is correct |
15 |
Correct |
26 ms |
1928 KB |
Output is correct |
16 |
Correct |
24 ms |
1948 KB |
Output is correct |
17 |
Correct |
696 ms |
6808 KB |
Output is correct |
18 |
Correct |
674 ms |
6704 KB |
Output is correct |
19 |
Correct |
678 ms |
6760 KB |
Output is correct |
20 |
Correct |
35 ms |
1996 KB |
Output is correct |
21 |
Correct |
18 ms |
1928 KB |
Output is correct |
22 |
Correct |
10 ms |
1876 KB |
Output is correct |
23 |
Correct |
8 ms |
1880 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
578 ms |
6708 KB |
Output is correct |
26 |
Correct |
540 ms |
6680 KB |
Output is correct |
27 |
Correct |
671 ms |
6824 KB |
Output is correct |
28 |
Correct |
620 ms |
6688 KB |
Output is correct |
29 |
Correct |
677 ms |
6804 KB |
Output is correct |
30 |
Correct |
729 ms |
7196 KB |
Output is correct |
31 |
Correct |
20 ms |
2004 KB |
Output is correct |
32 |
Correct |
6 ms |
1876 KB |
Output is correct |
33 |
Correct |
412 ms |
5652 KB |
Output is correct |
34 |
Correct |
6 ms |
1876 KB |
Output is correct |
35 |
Correct |
632 ms |
6636 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
545 ms |
6656 KB |
Output is correct |
39 |
Correct |
536 ms |
6744 KB |
Output is correct |
40 |
Correct |
555 ms |
6572 KB |
Output is correct |
41 |
Correct |
583 ms |
6628 KB |
Output is correct |
42 |
Correct |
548 ms |
6876 KB |
Output is correct |
43 |
Correct |
0 ms |
212 KB |
Output is correct |
44 |
Correct |
0 ms |
212 KB |
Output is correct |
45 |
Correct |
0 ms |
212 KB |
Output is correct |
46 |
Correct |
0 ms |
212 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
566 ms |
6980 KB |
Output is correct |
50 |
Correct |
559 ms |
6768 KB |
Output is correct |
51 |
Correct |
572 ms |
6696 KB |
Output is correct |
52 |
Correct |
548 ms |
6720 KB |
Output is correct |
53 |
Correct |
697 ms |
6808 KB |
Output is correct |
54 |
Correct |
635 ms |
6700 KB |
Output is correct |
55 |
Correct |
669 ms |
6588 KB |
Output is correct |
56 |
Correct |
24 ms |
2004 KB |
Output is correct |
57 |
Correct |
28 ms |
1996 KB |
Output is correct |
58 |
Correct |
687 ms |
5440 KB |
Output is correct |
59 |
Correct |
748 ms |
5424 KB |
Output is correct |
60 |
Correct |
789 ms |
5452 KB |
Output is correct |
61 |
Correct |
657 ms |
5448 KB |
Output is correct |
62 |
Correct |
769 ms |
5432 KB |
Output is correct |
63 |
Correct |
742 ms |
5536 KB |
Output is correct |
64 |
Execution timed out |
1084 ms |
5024 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |