| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 811980 | 2023-08-07T06:40:06 Z | vjudge1 | Olympic Bus (JOI20_ho_t4) | C++17 | 1000 ms | 10756 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e4 + 9 , mod = 1e9 + 7;
ll d[209][209] ,us[N][209] , a[N] = {}, dp[N] , b[N] , c[N] , p[N];
vector<int>v[N][2];
void dijkstra(int x , int k,int p , int o , int n){
ll i , j , m , s , f ,l , r , y;
for(i = 1; i <= n; i++){
d[i][p] = 1e15;
::p[i] = 0;
}
priority_queue<pair<ll,int>>pq;
d[x][p] = 0;
pq.push({0 , x});
while(!pq.empty()){
x = pq.top().se , f = pq.top().fi;
pq.pop();
if(d[x][p] != f){
continue;
}
for(auto to : v[x][k]){
if(to == o){
continue;
}
if(k == 0)
y = b[to];
else
y = a[to];
if(d[x][p] + c[to] < d[y][p]){
::p[y]= to;
d[y][p] = d[x][p] + c[to];
pq.push({d[y][p] , y});
}
}
}
for(i = 1; i <= n; i++)
us[::p[i]][p] = 1;
}
ll check[4] = {};
void get(int i , int x, int n){
check[x] = us[i][x];
if(us[i][x]){
if(x == 0)
dijkstra(1 , 0 , 0 , i, n);
if(x == 1)
dijkstra(1 , 1 , 1 , i, n);
if(x == 2)
dijkstra(n , 0 , 2 , i , n);
if(x == 3)
dijkstra(n , 1 , 3 , i , n);
}
}
void solve(){
ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn = 1e18 , mx = 0;
cin>>n>>m;
for(i = 1; i <= m; i++){
cin>>a[i]>>b[i]>>c[i]>>dp[i];
v[a[i]][0].pb(i);
v[b[i]][1].pb(i);
}
dijkstra(1 , 0 , 0 , -1, n);
dijkstra(1 , 1 , 1 , -1, n);
dijkstra(n , 0 , 2 , -1 , n);
dijkstra(n , 1 , 3 , -1 , n);
//cout<<d[1][2]<<"\n";
mn = d[n][0] + d[1][2];
//cout<<mn<<"\n";
for(i = 1; i <= m; i++){
for(j = 0; j < 4; j++)
check[j] = 0;
get(i , 0 , n);
get(i , 1 , n);
get(i , 2 , n);
get(i , 3 , n);
//if(i == 3){
// cout<<a[i]<<" "<<b[i]<<" "<<"\n";
// cout<<b[i]<<" "<<d[b[i]][0]<<" "<<"\n";
// cout<<a[i]<<" "<<d[a[i]][3]<<" "<<"\n";
//}
x = min(d[n][0] , d[b[i]][0] + d[a[i]][3] + c[i]);
y= min(d[1][2] , d[b[i]][2] + d[a[i]][1] + c[i]);
//cout<<x<<" "<<y<<"\n";
mn = min(mn , x + y + dp[i]);
if(check[0])
dijkstra(1 , 0 , 0 , -1, n);
if(check[1])
dijkstra(1 , 1 , 1 , -1, n);
if(check[2])
dijkstra(n , 0 , 2 , -1 , n);
if(check[3])
dijkstra(n , 1 , 3 , -1 , n);
}
if(mn >= 1e15)
mn = -1;
cout<<mn<<"\n";
}
int main(){
TL;
/* #ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 61 ms | 4600 KB | Output is correct |
| 2 | Correct | 3 ms | 3284 KB | Output is correct |
| 3 | Execution timed out | 1076 ms | 4600 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1072 ms | 7452 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 34 ms | 4564 KB | Output is correct |
| 2 | Correct | 4 ms | 3412 KB | Output is correct |
| 3 | Correct | 385 ms | 10560 KB | Output is correct |
| 4 | Correct | 3 ms | 3412 KB | Output is correct |
| 5 | Correct | 500 ms | 10756 KB | Output is correct |
| 6 | Correct | 1 ms | 2644 KB | Output is correct |
| 7 | Correct | 1 ms | 2644 KB | Output is correct |
| 8 | Correct | 100 ms | 8312 KB | Output is correct |
| 9 | Correct | 101 ms | 8284 KB | Output is correct |
| 10 | Correct | 333 ms | 9820 KB | Output is correct |
| 11 | Correct | 318 ms | 9912 KB | Output is correct |
| 12 | Correct | 318 ms | 9868 KB | Output is correct |
| 13 | Correct | 1 ms | 2644 KB | Output is correct |
| 14 | Correct | 1 ms | 2644 KB | Output is correct |
| 15 | Correct | 1 ms | 2644 KB | Output is correct |
| 16 | Correct | 1 ms | 2644 KB | Output is correct |
| 17 | Correct | 1 ms | 2644 KB | Output is correct |
| 18 | Correct | 1 ms | 2644 KB | Output is correct |
| 19 | Correct | 364 ms | 10700 KB | Output is correct |
| 20 | Correct | 289 ms | 10444 KB | Output is correct |
| 21 | Correct | 296 ms | 10528 KB | Output is correct |
| 22 | Correct | 324 ms | 10564 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 61 ms | 4600 KB | Output is correct |
| 2 | Correct | 3 ms | 3284 KB | Output is correct |
| 3 | Execution timed out | 1076 ms | 4600 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |