제출 #1363655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363655		lucaskojima	Robot (JOI21_ho_t4)	C++17	0 / 100	145 ms	29160 KiB

Main

#include "bits/stdc++.h"

#define int long long

using namespace std;

const long long INF = LLONG_MAX;

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, m; cin >> n >> m;

  vector<vector<pair<int, int>>> f(n + 1), g(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    f[a].push_back({b, c});
    f[b].push_back({a, c});
    g[a].push_back({b, d});
    g[b].push_back({a, d});
  }

  for (int x = 1; x <= n; x++) {
    multiset<int> st;
    for (auto [k, c] : f[x])
      st.insert(c);
    for (auto [k, c] : f[x])
      if (st.count(c) == 1)
        g[x].push_back({k, 0});
  }

  using T = pair<int, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  vector<int> dist(n + 1, INF);

  auto push = [&](int x, int d) -> void {
    if (d < dist[x])
      pq.push({dist[x] = d, x});
  };
  push(1, 0);

  while (!pq.empty()) {
    auto [d, x] = pq.top(); pq.pop();
    if (dist[x] != d) continue;

    for (auto [k, dd] : g[x])
      push(k, d + dd);
  }

  cout << (dist[n] == INF ? -1 : dist[n]) << '\n';
  return 0;
}

• 서브태스크 1: 0 / 34
• 서브태스크 2: 0 / 24
• 서브태스크 3: 0 / 42