Submission #1173082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173082		lopkus	Toll (BOI17_toll)	C++20	0 / 100	275 ms	589824 KiB

toll

#include <bits/stdc++.h>+

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int k, n, m, Q;
  std::cin >> k >> n >> m >> Q;
  std::vector<std::pair<int,int64_t>> adj[n];
  for(int i = 1; i <= m; i++) {
    int64_t u, v, t;
    std::cin >> u >> v >> t;
    adj[u].push_back({v, t});
    adj[v].push_back({u, t});
  }
  std::vector<std::vector<int64_t>> dist(n, std::vector<int64_t>(n));
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      dist[i][j] = 1e18;
    }
  }
  for(int i = 0; i < n; i++) {
    std::priority_queue<std::pair<int64_t,int>> pq;
    pq.push({0, i});
    dist[i][i] = 0;
    std::vector<int> was(n);
    while(!pq.empty()) {
      int v = (pq.top()).second;
      int cost = - (pq.top()).first;
      pq.pop();
      if(was[v]) {
        continue;
      }
      was[v] = 1;
      for(auto [u, t] : adj[v]) {
        if(dist[i][u] > cost + t) {
          dist[i][u] = cost + t;
          pq.push({-dist[i][u], u});
        }
      }
    }
  }
  while(Q--) {
    int u, v;
    std::cin >> u >> v;
    std::cout << (dist[u][v] == 1e18 ? - 1 : dist[u][v]) << "\n";
  }
}

Compilation message (stderr)

toll.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>+
      |                         ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44