oj.uz

Submission #964246

# Submission time Handle Problem Language Result Execution time Memory
964246 2024-04-16T13:28:59 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 5468 KB 
#include<bits/stdc++.h>
#define int long long
#define nl endl
using namespace std;
 
multiset<pair<int,int> > graph[201];
 
int Dijkstra(int u, int v){
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    vector<int> vis(201, 0);
    vector<int> dist(201, 1e18);
 
    dist[u] = 0;
    pq.push(make_pair(0, u));
 
    while(!pq.empty()){
        int p = pq.top().second;
        int dis = pq.top().first;
        pq.pop();
 
        if(vis[p]) continue;
        vis[p] = 1;
 
        for(auto ch : graph[p]){
            if(dis + ch.second < dist[ch.first]){
                dist[ch.first] = dis + ch.second;
                pq.push(make_pair(dist[ch.first], ch.first));
            }
        }
    }
 
    return dist[v];
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
 
    int n, m;
    cin>>n>>m;
 
    vector<vector<int> > dist(n+1, vector<int>(n+1, 1e18));
    int U[m], V[m], c[m], d[m];
    for(int i=0; i<m; i++){
        cin>>U[i]>>V[i]>>c[i]>>d[i];
        graph[U[i]].insert(make_pair(V[i], c[i]));
        dist[U[i]][V[i]] = min(c[i], dist[U[i]][V[i]]);
    }
    for(int i=1; i<=n; i++) dist[i][i] = 0;
 
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
 
    int ans = dist[1][n] + dist[n][1];
    //cout<<ans<<nl;
    for(int i=0; i<m; i++){
        int u = U[i], v = V[i];
    
 
        graph[u].erase(graph[u].find(make_pair(v, c[i])));
        graph[v].insert(make_pair(u, c[i]));
 
        ans = min(ans, Dijkstra(1, n) + Dijkstra(n, 1) + d[i]);
        //cout<<i<<" "<<Dijkstra(1, n) + Dijkstra(n, 1) + d[i]<<nl;
 
        graph[u].insert(make_pair(v, c[i]));
        graph[v].erase(graph[v].find(make_pair(u, c[i])));
    }
 
    if(ans >= 1e18) cout<<-1;
    else cout<<ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 856 KB Output is correct
2 Correct 7 ms 812 KB Output is correct
3 Correct 52 ms 892 KB Output is correct
4 Correct 58 ms 860 KB Output is correct
5 Correct 18 ms 348 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 13 ms 344 KB Output is correct
10 Correct 82 ms 884 KB Output is correct
11 Correct 83 ms 856 KB Output is correct
12 Correct 79 ms 888 KB Output is correct
13 Correct 32 ms 856 KB Output is correct
14 Correct 33 ms 904 KB Output is correct
15 Correct 33 ms 856 KB Output is correct
16 Correct 35 ms 856 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 5468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 856 KB Output is correct
2 Correct 9 ms 820 KB Output is correct
3 Execution timed out 1061 ms 5108 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 856 KB Output is correct
2 Correct 7 ms 812 KB Output is correct
3 Correct 52 ms 892 KB Output is correct
4 Correct 58 ms 860 KB Output is correct
5 Correct 18 ms 348 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 13 ms 344 KB Output is correct
10 Correct 82 ms 884 KB Output is correct
11 Correct 83 ms 856 KB Output is correct
12 Correct 79 ms 888 KB Output is correct
13 Correct 32 ms 856 KB Output is correct
14 Correct 33 ms 904 KB Output is correct
15 Correct 33 ms 856 KB Output is correct
16 Correct 35 ms 856 KB Output is correct
17 Execution timed out 1068 ms 5468 KB Time limit exceeded
18 Halted 0 ms 0 KB -