Submission #696630

#	Time	Username	Problem	Language	Result	Execution time	Memory
696630		minhnhatnoe	Autobus (COCI22_autobus)	C++14	70 / 70	103 ms	488 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll add(ll x, ll y) {
    if (LLONG_MAX - x <= y) return LLONG_MAX;
    return x + y;
}
vector<vector<ll>> operator*(vector<vector<ll>> &a, vector<vector<ll>> &b){
    vector<vector<ll>> c(a.size(), vector<ll> (a.size(), LLONG_MAX));
    for (int i=0; i<a.size(); i++){
        for (int j=0; j<a.size(); j++){
            for (int k=0; k<a.size(); k++){
                c[i][j] = min(c[i][j], add(a[i][k], b[k][j]));
            }
        }
    }
    return c;
}
vector<vector<ll>> binpow(vector<vector<ll>> a, int k){
    vector<vector<ll>> r(a.size(), vector<ll> (a.size(), LLONG_MAX));
    for (int i=0; i<a.size(); i++) r[i][i] = 0;
    for (; k; k >>= 1, a = a*a)
        if (k&1) r = r*a;
    return r;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<ll>> a(n, vector<ll> (n, LLONG_MAX));
    for (int i=0; i<m; i++){
        ll u, v, t; cin >> u >> v >> t;
        a[u-1][v-1] = min(a[u-1][v-1], t);
    }
    for (int i=0; i<n; i++) a[i][i] = 0;
    int k; cin >> k;
    a = binpow(a, k);
    int q; cin >> q;
    while (q--){
        int u, v; cin >> u >> v;
        ll r = a[u-1][v-1];
        if (r == LLONG_MAX){
            cout << "-1\n";
        }
        else{
            cout << r << "\n";
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<std::vector<long long int> > operator*(std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
Main.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
Main.cpp:11:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int j=0; j<a.size(); j++){
      |                       ~^~~~~~~~~
Main.cpp:12:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |             for (int k=0; k<a.size(); k++){
      |                           ~^~~~~~~~~
Main.cpp: In function 'std::vector<std::vector<long long int> > binpow(std::vector<std::vector<long long int> >, int)':
Main.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i=0; i<a.size(); i++) r[i][i] = 0;
      |                   ~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15