oj.uz

Submission #745535

# Submission time Handle Problem Language Result Execution time Memory
745535 2023-05-20T10:18:38 Z Pacybwoah Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 75 ms 3800 KB 
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<ll,pair<ll,ll>>>> graph(n+1);
    int a,b,c,d;
    vector<vector<ll>> dist(n+1,vector<ll>(n+1,1e18));
    for(int i=1;i<=n;i++) dist[i][i]=0;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c>>d;
        graph[a].push_back(make_pair(b,make_pair(c,d)));
        dist[a][b]=min(dist[a][b],1ll*c);
    }
    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]);
            }
        }
    }
    ll ans=dist[1][n]+dist[n][1];
    for(int i=1;i<=n;i++){
        for(auto x:graph[i]){
            ans=min(ans,min(dist[1][n],dist[1][x.first]+x.second.first+dist[i][n])+min(dist[n][1],dist[n][x.first]+x.second.first+dist[i][1])+x.second.second);
        }

    }
    if(ans>=1e18) cout<<-1;
    else cout<<ans;
    //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<i<<" "<<j<<" "<<dist[i][j]<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 9 ms 564 KB Output is correct
4 Correct 9 ms 688 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3424 KB Output is correct
2 Correct 57 ms 3532 KB Output is correct
3 Correct 65 ms 3656 KB Output is correct
4 Correct 10 ms 724 KB Output is correct
5 Correct 9 ms 572 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 9 ms 564 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 75 ms 3652 KB Output is correct
10 Correct 59 ms 3644 KB Output is correct
11 Correct 65 ms 3612 KB Output is correct
12 Correct 58 ms 3532 KB Output is correct
13 Correct 62 ms 3800 KB Output is correct
14 Correct 59 ms 3784 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 668 KB Output is correct
2 Correct 8 ms 596 KB Output is correct
3 Correct 47 ms 2608 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 61 ms 3284 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 9 ms 564 KB Output is correct
4 Correct 9 ms 688 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -