oj.uz

Submission #789731

# Submission time Handle Problem Language Result Execution time Memory
789731 2023-07-21T21:24:16 Z VMaksimoski008 Autobus (COCI22_autobus) C++14
0 / 70
 2 ms 340 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
#define each(x, v) for(auto &x : v)
#define mp make_pair

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Node = array<ll, 3>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int32_t main() {
    setIO();

    int n, m;
    cin >> n >> m;
    vector<vector<pii> > graph(n+1);
    for(int i=0; i<m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({ b, w });
    }

    int k, q;
    cin >> k >> q;

    vector<vector<ll> > dist(n+1, vector<ll>(n+1, 1e18));
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    for(int i=1; i<=n; i++) {
        dist[i][i] = 0;
        pq.push({ 0, 0, i });
        vector<bool> vis(n+1, false);

        while(!pq.empty()) {
            ll d = pq.top().at(0);
            int c = pq.top().at(1);
            int u = pq.top().at(2);
            pq.pop();

            if(vis[u]) continue;
            vis[u] = true;

            if(c == k) continue;
            for(pii &v : graph[u]) {
                if(dist[i][v.first] > dist[i][u] + v.second) {
                    dist[i][v.first] = dist[i][u] + v.second;
                    pq.push({ dist[i][v.first], c+1, v.first });
                }
            }
        }
    }

    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << (dist[a][b] == 1e18 ? -1 : dist[a][b]) << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:55:16: warning: unused variable 'd' [-Wunused-variable]
   55 |             ll d = pq.top().at(0);
      |                ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -