Submission #953544

#	Time	Username	Problem	Language	Result	Execution time	Memory
953544		Trisanu_Das	Robot (JOI21_ho_t4)	C++17	34 / 100	3044 ms	469212 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, 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';
}

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