제출 #1324805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324805		riafhasan2010	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	970 ms	57384 KiB

commuter_pass

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

const ll inf = 1e17;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m; cin >> n >> m;
  int s, t, u, v; cin >> s >> t >> u >> v;
  vector<pair<int, int>> g[n + 1];
  for (int i = 1; i <= m; i++) {
    int a, b, c; cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<pair<int, ll>> path[n + 1];
  vector<ll> st(n + 1, inf);
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  pq.push({0, s});
  st[s] = 0;
  while (!pq.empty()) {
    auto [w, a] = pq.top(); pq.pop();
    for (auto [b, c] : g[a]) {
      path[b].push_back({a, 1ll * w + c});
      if (1ll * w + c < st[b]) {
        st[b] = 1ll * w + c;
        pq.push({1ll * w + c, b});
      }
    }
  }
  map<pair<int, int>, bool> mp;
  for (int i = 1; i <= n; i++) {
    for (auto [j, w] : path[i]) {
      if (w == st[i]) {
        mp[{i, j}] = 1;
        mp[{j, i}] = 1;
      }
    }
  }
  for (int i = 1; i <= n; i++) st[i] = inf;
  pq.push({0, u});
  st[u] = 0;
  while (!pq.empty()) {
    auto [w, a] = pq.top(); pq.pop();
    for (auto [b, c] : g[a]) {
      if (mp[{a, b}] or mp[{b, a}]) c = 0;
      if (1ll * w + c < st[b]) {
        st[b] = 1ll * w + c;
        pq.push({1ll * w + c, b});
      }
    }
  }
  cout << st[v] << '\n';
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45