Submission #1163296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163296		Johan	Evacuation plan (IZhO18_plan)	C++20	23 / 100	322 ms	32220 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

const int MAX = 3e4 + 6;
const int LOG = 25;
const int inf = 1e18;
const int mod = 999983;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, k, q;
  cin >> n >> m;
  vector < int > d(n + 1, inf);
  vector < vector < pair < int , int > > > adj(n + 1);
  priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;
  for(int i = 1; i <= m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({w, v});
    adj[v].push_back({w, u});
  }
  cin >> k;
  vector < int > g(k + 1);
  for(int i = 1; i <= k; i++){
    cin >> g[i];
    d[g[i]] = 0; pq.push({d[g[i]], g[i]});
  }
  while(pq.size()){
    int w = pq.top().first;
    int from = pq.top().second;
    pq.pop();
    if(w != d[from])  continue;
    for(pair < int , int > p : adj[from]){
      int we = p.first;
      int to = p.second;
      if(d[to] > d[from] + we){
        d[to] = d[from] + we;
        pq.push({d[to], to});
      }
    }
  }
  cin >> q;
  while(q--){
    int u, v;
    cin >> u >> v;
    cout << min(d[u], d[v]) << endl;
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46