Submission #513846

#	Time	Username	Problem	Language	Result	Execution time	Memory
513846		jesus_coconut	Robot (JOI21_ho_t4)	C++17	34 / 100	3021 ms	281248 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a), end(a)
#define F first
#define S second
using namespace std;

using ll = long long;

struct Edge {
  int to;
  int c;
  ll p;
};

int const N = 100005;

int n, m;
vector<vector<Edge>> adj;
set<pair<int, int>> bio;
ll cost[2 * N];

struct Item {
  ll cur_cost;
  int ver;
  int par;
  bool friend operator>(Item const &lhs, Item const &rhs) {
	return lhs.cur_cost > rhs.cur_cost;
  }
};

void load() {
  cin >> n >> m;
  adj.resize(n);
  for (int i = 0; i < m; ++i) {
	int u, v, c, p;
	cin >> u >> v >> c >> p;
	--u; -- v;
	adj[u].pb({v, c, p});
	adj[v].pb({u, c, p});
  }
}

ll solve() {

  priority_queue<Item, vector<Item>, greater<>> pq;
  pq.push({0, 0, -1});
  while (!pq.empty()) {
	auto [cur_cost, ver, par] = pq.top();
	if (ver == n - 1) return cur_cost;
	pq.pop();
	if (bio.count({par, ver})) continue;
	bio.emplace(par, ver);
	for (auto [u, col, price] : adj[ver]) {
	  if (par == u) continue;
	  cost[col] += price;
	}
	for (auto [u, col, price] : adj[ver]) {
	  if (!bio.count({-1, u})) {
		pq.push({cur_cost + cost[col] - price, u, -1});

	  }
	  if (!bio.count({ver, u})) {
		pq.push({cur_cost + price, u, ver});
	  }
	}
	for (auto [u, col, price] : adj[ver]) {
	  cost[col] = 0;
	}
  }
  return -1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);


  load();
  cout << solve() << '\n';

  return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42