Submission #1133229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133229		JelalTkm	Evacuation plan (IZhO18_plan)	C++20	41 / 100	4093 ms	37448 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 3e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>> ());
    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      g[u].push_back(make_pair(v, w));
      g[v].push_back(make_pair(u, w));
    }

    int k;
    cin >> k;
    vector<int> dist(n + 1, INF);
    set<pair<int, int>> q;
    for (int i = 0; i < k; i++) {
      int u;
      cin >> u;
      dist[u] = 0;
      q.insert({0, u});
    }

    vector<bool> visited(n + 1);

    while (!q.empty()) {
      int v = (*q.begin()).second;
      q.erase(q.begin());
      if (!visited[v])
        for (auto i : g[v]) {
          dist[i.first] = min(dist[i.first], dist[v] + i.second);
          if (!visited[i.first])
            q.insert({dist[i.first], i.first});
        }
      visited[v] = 1;
    }

    // for (int i = 1; i <= n; i++)
    //   cout << i << " " << dist[i] << '\n';

    int qu;
    cin >> qu;
    while (qu--) {
      int st, fn;
      cin >> st >> fn;
      set<pair<int, int>> q;
      q.insert({-dist[st], st});
      map<int, bool> vs;
      int ans = 0;
      while (!q.empty()) {
        int v = (*q.begin()).second;
        int ds = (*q.begin()).first;
        if (fn == v) {
          ans = max(ans, abs(ds));
          break;
        }
        q.erase(q.begin());
        if (!vs[v])
          for (auto i : g[v]) {
            if (!vs[i.first])
              q.insert({max(ds, -dist[i.first]), i.first});
          }
        vs[v] = 1;
      }

      cout << ans << '\n';
    }
  }

  return 0;
}

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