oj.uz

Submission #244604

# Submission time Handle Problem Language Result Execution time Memory
244604 2020-07-04T11:54:00 Z kimbj0709 Toll (BOI17_toll) C++14
10 / 100
 88 ms 9080 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 50050
#define f first
#define s second
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k,no_of_vertex,no_of_edge,no_of_query;
    int input1,input2,input3;
    cin >> k >> no_of_vertex >> no_of_edge >> no_of_query;
    vector<vector<pair<int,int> > > adj(maxn);
    for(int i=0;i<no_of_edge;i++){
        cin >> input1 >> input2 >> input3;
        adj[input1].push_back({input2,input3});
    }
    vector<int> dist(maxn,INT_MAX);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1;
    dist[0] = 0;
    q1.push({0,0});
    while(q1.size()!=0){
        pair<int,int> a = q1.top();
        q1.pop();
        for(auto j:adj[a.s]){
            if(dist[j.f]>a.f+j.s){
                dist[j.f] = a.f+j.s;
                q1.push({dist[j.f],j.f});
            }
        }
    }
    for(int i=0;i<no_of_query;i++){
        cin >> input1 >> input2;
        if(dist[input2]==INT_MAX){
            cout << -1 << "\n";
        }
        else{
            cout << dist[input2] << "\n";
        }
    }


}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6136 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct
3 Correct 5 ms 1920 KB Output is correct
4 Correct 7 ms 1920 KB Output is correct
5 Correct 6 ms 1920 KB Output is correct
6 Correct 6 ms 1920 KB Output is correct
7 Correct 8 ms 2048 KB Output is correct
8 Correct 9 ms 2176 KB Output is correct
9 Correct 27 ms 4344 KB Output is correct
10 Correct 88 ms 8184 KB Output is correct
11 Correct 49 ms 6444 KB Output is correct
12 Correct 36 ms 5248 KB Output is correct
13 Correct 71 ms 9080 KB Output is correct
14 Correct 45 ms 6008 KB Output is correct
15 Correct 40 ms 5244 KB Output is correct
16 Correct 36 ms 5112 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -