제출 #685734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685734		ethening	Robot (JOI21_ho_t4)	C++17	0 / 100	189 ms	76728 KiB

Main

#include "bits/stdc++.h"
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;

#define DEBUG 0

const ll INF = 1000'000'000'000'000'000ll;

const int MAXN = 100000;
const int MAXM = 200000;

int n, m;

unordered_map<int, int> s[MAXN + 5];
unordered_map<int, ll> csum[MAXN + 5];

int a[MAXN + 5][4];

struct edge {
	int fr;
	int to;
	ll weight;
} e[4 * MAXM + 5];

vector<int> v[4 * MAXM + 5];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
		if (s[a[i][0]].find(0) == s[a[i][0]].end()) {
			s[a[i][0]][0] = ++cnt;
		}
		if (s[a[i][0]].find(a[i][2]) == s[a[i][0]].end()) {
			s[a[i][0]][a[i][2]] = ++cnt;
		}
		if (csum[a[i][0]].find(a[i][2]) == csum[a[i][0]].end()) {
			csum[a[i][0]][a[i][2]] = a[i][3];
		}
		else csum[a[i][0]][a[i][2]] += a[i][3];
		if (s[a[i][1]].find(0) == s[a[i][1]].end()) {
			s[a[i][1]][0] = ++cnt;
		}
		if (s[a[i][1]].find(a[i][2]) == s[a[i][1]].end()) {
			s[a[i][1]][a[i][2]] = ++cnt;
		}
		if (csum[a[i][1]].find(a[i][2]) == csum[a[i][1]].end()) {
			csum[a[i][1]][a[i][2]] = a[i][3];
		}
		else csum[a[i][1]][a[i][2]] += a[i][3];
	}

	if (DEBUG) {
		for (int i = 1; i <= n; i++) {
			for (auto [dex, val] : s[i]) {
				cout << "i: " << i << " col: " << dex << " index: " << val << endl;
			}
		}
	}

	int ecnt = 0;
	for (int i = 1; i <= m; i++) {
		int col = a[i][2];
		int fr = a[i][0];
		int to = a[i][1];
		int node10 = s[fr][0];
		int node1c = s[fr][col];
		int node20 = s[to][0];
		int node2c = s[to][col];
		e[++ecnt] = {.fr = node10, .to = node20, .weight = min((ll)a[i][3], csum[fr][col] - a[i][3])};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node10, .to = node2c, .weight = 0};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node1c, .to = node20, .weight = csum[fr][col] - a[i][3]};
		v[node1c].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node10, .weight = min((ll)a[i][3], csum[to][col] - a[i][3])};
		v[node20].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node1c, .weight = 0};
		v[node20].push_back(ecnt);
		e[++ecnt] = {.fr = node2c, .to = node10, .weight = csum[to][col] - a[i][3]};
		v[node2c].push_back(ecnt);
	}

	if (DEBUG) {
		for (int i = 1; i <= ecnt; i++) {
			cout << "fr: " << e[i].fr << " to: " << e[i].to << " we: " << e[i].weight << endl;
		}
	}

	int source = s[1][0];
	int dest = s[n][0];
	vector<ll> dist(cnt + 5, INF);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	Q.push({0, source});
	while (!Q.empty()) {
		auto [curDist, cur] = Q.top();
		Q.pop();
		if (dist[cur] > curDist) continue;
		if (cur == dest) break;
		for (auto eg: v[cur]) {
			if (dist[cur] + e[eg].weight < dist[e[eg].to]) {
				dist[e[eg].to] = dist[cur] + e[eg].weight;
				Q.push({dist[e[eg].to], e[eg].to});
			}
		}
	}
	if (DEBUG) {
		for (int i = 1; i <= cnt; i++) {
			cout << "dist " << i << " : " << dist[i] << endl;
		}
	}
	if (dist[dest] == INF) dist[dest] = -1;
	cout << dist[dest] << "\n";
}

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