oj.uz

Submission #645941

# Submission time Handle Problem Language Result Execution time Memory
645941 2022-09-28T10:18:41 Z mychecksedad Toll (BOI17_toll) C++17
10 / 100
 63 ms 29176 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, m, k, qq;
vector<pair<int, int>> g[N];
     
void solve(){
    cin >> k >> n >> m >> qq;
    for(int i = 0; i < m; ++i){
        int u, v, e; cin >> u >> v >> e;
        g[u].pb({v, e});
    }
    priority_queue<pair<ll, int>> q;
    q.push({0, 0});
    vector<bool> used(n + 1);
    vector<ll> dist(n + 1, 1e18);
    dist[0] = 0;
    while(!q.empty()){
        int v = q.top().second; q.pop();
        if(used[v]) continue;
        used[v] = 1;
        for(auto u: g[v]){
            if(dist[u.first] > dist[v] + u.second){
                dist[u.first] = dist[v] + u.second;
                q.push({-dist[u.first], u.first});
            }
        }
    }
    for(;qq--;){
        int a, b; cin >> a >> b;
        if(dist[b] == 1e18) cout << "-1\n";
        else cout << dist[b] << '\n';
    }   
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:55:16: warning: unused variable 'aa' [-Wunused-variable]
   55 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 25780 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 39 ms 25768 KB Output is correct
2 Correct 11 ms 23792 KB Output is correct
3 Correct 11 ms 23700 KB Output is correct
4 Correct 12 ms 23808 KB Output is correct
5 Correct 12 ms 23708 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 14 ms 23916 KB Output is correct
9 Correct 31 ms 26616 KB Output is correct
10 Correct 60 ms 29004 KB Output is correct
11 Correct 45 ms 27476 KB Output is correct
12 Correct 36 ms 26976 KB Output is correct
13 Correct 63 ms 29176 KB Output is correct
14 Correct 42 ms 27124 KB Output is correct
15 Correct 39 ms 26592 KB Output is correct
16 Correct 37 ms 26488 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23764 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 25780 KB Output isn't correct
2 Halted 0 ms 0 KB -