| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 975053 |
2024-05-04T10:42:26 Z |
berr |
Olympic Bus (JOI20_ho_t4) |
C++17 |
|
120 ms |
18780 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);
queue<int> pq[N];
vector<int> dijkstra_rev(int v, int skip){
vector<int> dist(N, INF);
dist[v] = 0;
pq[0].push(v);
int q=0;
while(q<N){
if(!pq[q].size()) q++;
else{
int v=pq[q].front(); pq[q].pop();
if(v==skip||dist[v] != q) continue;
for(auto [i, l, j]: g_rev[v]){
if(dist[i] > q+l){
dist[i] = q+l;
pq[dist[i]].push(i);
}
}
}
}
return dist;
}
vector<int> dijkstra(int v, int skip){
vector<int> dist(N, INF);
dist[v]=0;
pq[0].push(v);
int q=0;
while(q<N){
if(!pq[q].size()) q++;
else{
int v=pq[q].front(); pq[q].pop();
if(v==skip||dist[v] != q) continue;
for(auto [i, l, j]: g[v]){
if(dist[i] > q+l){
dist[i] = q+l;
pq[dist[i]].push(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 |
37 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3864 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5212 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
18780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
3928 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3932 KB |
Output is correct |
| 3 |
Correct |
110 ms |
9700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 5 |
Correct |
120 ms |
11280 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2592 KB |
Output is correct |
| 8 |
Correct |
55 ms |
11488 KB |
Output is correct |
| 9 |
Correct |
57 ms |
11636 KB |
Output is correct |
| 10 |
Correct |
103 ms |
11116 KB |
Output is correct |
| 11 |
Correct |
89 ms |
11092 KB |
Output is correct |
| 12 |
Correct |
93 ms |
11644 KB |
Output is correct |
| 13 |
Correct |
1 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 |
2652 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
104 ms |
11536 KB |
Output is correct |
| 20 |
Correct |
94 ms |
10936 KB |
Output is correct |
| 21 |
Correct |
90 ms |
11284 KB |
Output is correct |
| 22 |
Correct |
98 ms |
11204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3864 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5212 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
