Submission #1122385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122385		qrn	Autobus (COCI22_autobus)	C++14	0 / 70	1054 ms	1876 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mxN = 2e5 + 5, L = 20, mxA = 1e6 + 35;

struct edge{
    intt l, r;
};

vector<vector<intt>>graph;
vector<intt>visited(mxN);
vector<intt>path;
map<pair<intt,intt>,intt>vals;
intt ans = mxA;

void dfs(intt u, intt end, intt k) {
    visited[u] = true;
    path.pb(u);

    if (u == end) {
        if(path.size()-1 <= k) {
            intt sum = 0;
            for(int i = 1; i < path.size(); i++) {
                // cout << path[i] << " ";
                sum += vals[{min(path[i-1],path[i]),max(path[i-1],path[i])}];
            }
            ans = min(ans, sum);
            // cout << endl;
        } else {
            // for(auto u : path) cout << u << " ";
            // cout << endl;
        }
    } else {
        for (auto v : graph[u]) {
            if (!visited[v]) {
                dfs(v, end, k);
            }
        }
    }
  
    
    path.pop_back();
    visited[u] = false;
}

void solve() {
    intt n, m;
    cin >> n >> m;
    
    graph.resize(n + 1);
    for(intt i = 1; i <= m; i++) {
        intt a, b, w;
        cin >> a >> b >> w;
        graph[a].pb(b);
        vals[{min(a,b), max(a,b)}] = w;
    }
    
    intt k, q;
    cin >> k >> q;
    while(q--) {
        intt l, r;
        cin >> l >> r;
        dfs(l, r, k);
        if(ans == mxA) cout << -1 << endl;
        else
        cout << ans << endl;
        ans = mxA;
    }
}

int main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:31:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |         if(path.size()-1 <= k) {
      |            ~~~~~~~~~~~~~~^~~~
Main.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int i = 1; i < path.size(); i++) {
      |                            ~~^~~~~~~~~~~~~

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