# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
975049 |
2024-05-04T10:38:51 Z |
berr |
Olympic Bus (JOI20_ho_t4) |
C++17 |
|
959 ms |
11444 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=205, INF=1e16;
vector<int> all[N][N], all2[N][N];
vector<vector<int>> a, b, c, d;
vector<vector<array<int, 3>>> g(N), g_rev(N);
vector<int> dijkstra_rev(int v, int skip){
vector<int> dist(N, INF);
dist[v] = 0;
priority_queue<array<int, 2>> pq;
pq.push({0, v});
while(pq.size()){
auto [cost, v]=pq.top();
pq.pop(); cost*=-1;
if(v==skip||dist[v] != cost) continue;
for(auto [i, l, j]: g_rev[v]){
if(dist[i] > cost+l){
dist[i] = cost+l;
pq.push({-dist[i], i});
}
}
}
return dist;
}
vector<int> dijkstra(int v, int skip){
vector<int> dist(N, INF);
dist[v]=0;
priority_queue<array<int, 2>> pq;
pq.push({0, v});
while(pq.size()){
auto [cost, v]=pq.top();
pq.pop(); cost*=-1;
if(v==skip||dist[v] != cost) continue;
for(auto [i, l, j]: g[v]){
if(dist[i] > cost+l){
dist[i] = cost+l;
pq.push({-dist[i], i});
}
}
}
return dist;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<array<int, 3>> e(m);
vector<int> di(m);
int cnt =0;
for(auto &[u, v, c]: e){
cin >> u >> v >> c >> di[cnt];
u--; v--;
g[u].push_back({v, c, cnt});
g_rev[v].push_back({u, c, cnt});
all[u][v].push_back(cnt);
all2[u][v].push_back(cnt);
cnt++;
}
for(int i=0; i<n; i++){
sort(g[i].begin(), g[i].end(), [&](auto x, auto y){
return x[1] < y[1];
});
sort(g_rev[i].begin(), g_rev[i].end(), [&](auto x, auto y){
return x[1] < y[1];
});
for(int l=0; l<n; l++){
sort(all[i][l].begin(), all[i][l].end(), [&](int x, int y){
return e[x][2] < e[y][2];
});
sort(all2[i][l].begin(), all2[i][l].end(), [&](int x, int y){
return e[x][2]+di[x] < e[y][2]+di[y];
});
}
}
// a = 1 -> i, b = i -> n
// c = i -> 1 without x
// d = n -> i without x
for(int i=0; i<=n; i++){
a.push_back(dijkstra(0, i));
b.push_back(dijkstra_rev(n-1, i));
c.push_back(dijkstra_rev(0, i));
d.push_back(dijkstra(n-1, i));
}
int ans=INF;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==j) continue;
if(a[j][i]==INF||b[i][j]==INF) continue;
int sum=a[j][i]+b[i][j];
int tsum=sum, ksum=INF;
int g=0;
for(auto k: all2[j][i]){
g++;
if(g==3) break;
sum=tsum;
sum+=e[k][2];
sum+=di[k];
if(all[j][i].size()>1){
if(k==all[j][i][0])
ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][1]][2]);
else
ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][0]][2]);
}
ans=min(ans, sum+c[i][j]+d[j][i]+e[k][2]);
// diğer değer
if(all[i][j].size()>0){
ans=min(ans, sum+c[i][j]+d[j][i]+e[all[i][j][0]][2]);
}
ksum=min(ksum, sum);
}
for(int g=0; g<n; g++){
if(g!=i&&g!=j){
ans=min(ans, ksum+d[j][g]+c[i][g]);
ans=min(ans, ksum+d[i][g]+c[j][g]);
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
//blocklanan edge i ve j arasında
if(i==j) continue;
if(d[j][i]==INF||c[i][j]==INF) continue;
int sum=d[j][i]+c[i][j];
int tsum=sum, ksum=INF;;
int g=0;
for(auto k: all2[j][i]){
g++;
if(g==3) break;
sum=tsum;
sum+=e[k][2];
sum+=di[k];
if(all[j][i].size()>1){
if(k==all[j][i][0])
ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][1]][2]);
else
ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][0]][2]);
}
ans=min(ans, sum+a[j][i]+b[i][j]+e[k][2]);
if(all[i][j].size()>0){
ans=min(ans, sum+a[j][i]+b[i][j]+e[all[i][j][0]][2]);
}
ksum=min(ksum, sum);
}
for(int g=0; g<n; g++){
if(g!=i&&g!=j){
ans=min(ans, ksum+b[j][g]+a[i][g]);
ans=min(ans, ksum+b[i][g]+a[j][g]);
}
}
}
}
ans = min(ans, a[n][n-1]+d[n][0]);
if(ans==INF) cout<<-1;
else cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
3932 KB |
Output is correct |
2 |
Correct |
3 ms |
3676 KB |
Output is correct |
3 |
Correct |
51 ms |
3960 KB |
Output is correct |
4 |
Correct |
53 ms |
3920 KB |
Output is correct |
5 |
Correct |
3 ms |
2652 KB |
Output is correct |
6 |
Correct |
3 ms |
3676 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2400 KB |
Output is correct |
10 |
Correct |
56 ms |
3960 KB |
Output is correct |
11 |
Correct |
57 ms |
3928 KB |
Output is correct |
12 |
Correct |
58 ms |
4180 KB |
Output is correct |
13 |
Correct |
18 ms |
3736 KB |
Output is correct |
14 |
Correct |
33 ms |
3932 KB |
Output is correct |
15 |
Correct |
29 ms |
3932 KB |
Output is correct |
16 |
Correct |
31 ms |
3932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
10700 KB |
Output is correct |
2 |
Correct |
155 ms |
10320 KB |
Output is correct |
3 |
Correct |
149 ms |
10832 KB |
Output is correct |
4 |
Correct |
52 ms |
3932 KB |
Output is correct |
5 |
Correct |
38 ms |
3676 KB |
Output is correct |
6 |
Correct |
4 ms |
3672 KB |
Output is correct |
7 |
Correct |
3 ms |
3676 KB |
Output is correct |
8 |
Correct |
1 ms |
2392 KB |
Output is correct |
9 |
Correct |
70 ms |
11088 KB |
Output is correct |
10 |
Correct |
69 ms |
11088 KB |
Output is correct |
11 |
Correct |
111 ms |
10684 KB |
Output is correct |
12 |
Correct |
108 ms |
10504 KB |
Output is correct |
13 |
Correct |
112 ms |
10580 KB |
Output is correct |
14 |
Correct |
111 ms |
11088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
3956 KB |
Output is correct |
2 |
Correct |
7 ms |
3672 KB |
Output is correct |
3 |
Correct |
105 ms |
9556 KB |
Output is correct |
4 |
Correct |
4 ms |
3672 KB |
Output is correct |
5 |
Correct |
103 ms |
11328 KB |
Output is correct |
6 |
Correct |
1 ms |
2404 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
48 ms |
11444 KB |
Output is correct |
9 |
Correct |
53 ms |
11116 KB |
Output is correct |
10 |
Correct |
118 ms |
10836 KB |
Output is correct |
11 |
Correct |
78 ms |
10700 KB |
Output is correct |
12 |
Correct |
94 ms |
11144 KB |
Output is correct |
13 |
Correct |
2 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
2 ms |
2396 KB |
Output is correct |
16 |
Correct |
2 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2392 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
88 ms |
11216 KB |
Output is correct |
20 |
Correct |
77 ms |
10836 KB |
Output is correct |
21 |
Correct |
86 ms |
10708 KB |
Output is correct |
22 |
Correct |
76 ms |
10404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
3932 KB |
Output is correct |
2 |
Correct |
3 ms |
3676 KB |
Output is correct |
3 |
Correct |
51 ms |
3960 KB |
Output is correct |
4 |
Correct |
53 ms |
3920 KB |
Output is correct |
5 |
Correct |
3 ms |
2652 KB |
Output is correct |
6 |
Correct |
3 ms |
3676 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2400 KB |
Output is correct |
10 |
Correct |
56 ms |
3960 KB |
Output is correct |
11 |
Correct |
57 ms |
3928 KB |
Output is correct |
12 |
Correct |
58 ms |
4180 KB |
Output is correct |
13 |
Correct |
18 ms |
3736 KB |
Output is correct |
14 |
Correct |
33 ms |
3932 KB |
Output is correct |
15 |
Correct |
29 ms |
3932 KB |
Output is correct |
16 |
Correct |
31 ms |
3932 KB |
Output is correct |
17 |
Correct |
160 ms |
10700 KB |
Output is correct |
18 |
Correct |
155 ms |
10320 KB |
Output is correct |
19 |
Correct |
149 ms |
10832 KB |
Output is correct |
20 |
Correct |
52 ms |
3932 KB |
Output is correct |
21 |
Correct |
38 ms |
3676 KB |
Output is correct |
22 |
Correct |
4 ms |
3672 KB |
Output is correct |
23 |
Correct |
3 ms |
3676 KB |
Output is correct |
24 |
Correct |
1 ms |
2392 KB |
Output is correct |
25 |
Correct |
70 ms |
11088 KB |
Output is correct |
26 |
Correct |
69 ms |
11088 KB |
Output is correct |
27 |
Correct |
111 ms |
10684 KB |
Output is correct |
28 |
Correct |
108 ms |
10504 KB |
Output is correct |
29 |
Correct |
112 ms |
10580 KB |
Output is correct |
30 |
Correct |
111 ms |
11088 KB |
Output is correct |
31 |
Correct |
56 ms |
3956 KB |
Output is correct |
32 |
Correct |
7 ms |
3672 KB |
Output is correct |
33 |
Correct |
105 ms |
9556 KB |
Output is correct |
34 |
Correct |
4 ms |
3672 KB |
Output is correct |
35 |
Correct |
103 ms |
11328 KB |
Output is correct |
36 |
Correct |
1 ms |
2404 KB |
Output is correct |
37 |
Correct |
1 ms |
2396 KB |
Output is correct |
38 |
Correct |
48 ms |
11444 KB |
Output is correct |
39 |
Correct |
53 ms |
11116 KB |
Output is correct |
40 |
Correct |
118 ms |
10836 KB |
Output is correct |
41 |
Correct |
78 ms |
10700 KB |
Output is correct |
42 |
Correct |
94 ms |
11144 KB |
Output is correct |
43 |
Correct |
2 ms |
2396 KB |
Output is correct |
44 |
Correct |
1 ms |
2396 KB |
Output is correct |
45 |
Correct |
2 ms |
2396 KB |
Output is correct |
46 |
Correct |
2 ms |
2396 KB |
Output is correct |
47 |
Correct |
1 ms |
2392 KB |
Output is correct |
48 |
Correct |
1 ms |
2396 KB |
Output is correct |
49 |
Correct |
88 ms |
11216 KB |
Output is correct |
50 |
Correct |
77 ms |
10836 KB |
Output is correct |
51 |
Correct |
86 ms |
10708 KB |
Output is correct |
52 |
Correct |
76 ms |
10404 KB |
Output is correct |
53 |
Correct |
171 ms |
10976 KB |
Output is correct |
54 |
Correct |
183 ms |
11148 KB |
Output is correct |
55 |
Correct |
172 ms |
11384 KB |
Output is correct |
56 |
Correct |
53 ms |
3964 KB |
Output is correct |
57 |
Correct |
57 ms |
3828 KB |
Output is correct |
58 |
Correct |
154 ms |
9724 KB |
Output is correct |
59 |
Correct |
147 ms |
9556 KB |
Output is correct |
60 |
Correct |
155 ms |
9740 KB |
Output is correct |
61 |
Correct |
141 ms |
9940 KB |
Output is correct |
62 |
Correct |
190 ms |
9916 KB |
Output is correct |
63 |
Correct |
163 ms |
9804 KB |
Output is correct |
64 |
Correct |
959 ms |
9896 KB |
Output is correct |
65 |
Correct |
859 ms |
10320 KB |
Output is correct |
66 |
Correct |
844 ms |
10372 KB |
Output is correct |
67 |
Correct |
27 ms |
7552 KB |
Output is correct |
68 |
Correct |
74 ms |
11444 KB |
Output is correct |
69 |
Correct |
76 ms |
11364 KB |
Output is correct |
70 |
Correct |
125 ms |
10912 KB |
Output is correct |
71 |
Correct |
113 ms |
10836 KB |
Output is correct |
72 |
Correct |
116 ms |
10664 KB |
Output is correct |
73 |
Correct |
120 ms |
11200 KB |
Output is correct |
74 |
Correct |
115 ms |
11208 KB |
Output is correct |