Submission #415897

#	Time	Username	Problem	Language	Result	Execution time	Memory
415897		egod1537	Robot (JOI21_ho_t4)	C++14	58 / 100	3075 ms	109180 KiB

Main

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
struct Line {
	int to, col;
	ll cost;
	int cc;
};
struct Q {
	int pos;
	ll cost;
};
bool operator<(const Q& a, const Q& b) {
	return a.cost > b.cost;
}

vector<vector<Line>> V;

vector<int> tidx;
vector<vector<int>> vidx;
vector<map<int, int>> cidx;

vector<vector<vector<Line>>> vcole;
vector<vector<int>> colcnt;
vector<vector<ll>> colsum;

vector<ll> dst;

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

	int n, m; cin >> n >> m;
	V.resize(n + 1); cidx.resize(n + 1);
	colcnt.resize(n + 1); colsum.resize(n + 1);
	vcole.resize(n + 1); vidx.resize(n + 1);
	tidx.resize(n + 1); cidx.resize(n + 1);
	int vnum = n + 1;
	for (int i = 0; i < m; i++) {
		int from, to, col; ll cost; cin >> from >> to >> col >> cost;
		if (cidx[from].find(col) == cidx[from].end()) {
			vidx[from].push_back(vnum++);
			cidx[from][col] = tidx[from]++;
			vcole[from].push_back(vector<Line>());
			colcnt[from].push_back(0); colsum[from].push_back(0);
		}
		if (cidx[to].find(col) == cidx[to].end()) {
			vidx[to].push_back(vnum++);
			cidx[to][col] = tidx[to]++;
			vcole[to].push_back(vector<Line>());
			colcnt[to].push_back(0); colsum[to].push_back(0);
		}

		int fromc = cidx[from][col], toc = cidx[to][col];
		colcnt[from][fromc]++, colsum[from][fromc] += cost;
		colcnt[to][toc]++, colsum[to][toc] += cost;

		vcole[from][fromc].push_back({ to, col, cost });
		vcole[to][toc].push_back({ from, col, cost });

		V[from].push_back({ to, col, cost, fromc });
		V[to].push_back({ from, col, cost, toc });
	}

	dst.resize(vnum + 1, 1e18);
	for (int i = n + 1; i < vnum; i++) V.push_back(vector<Line>());

	for (int i = 1; i <= n; i++) {
		int sz = V[i].size();
		for (int j = 0; j < sz; j++) {
			Line& w = V[i][j];
			int idx = cidx[w.to][w.col];
			V[i].push_back({ vidx[w.to][idx], w.col, 0, idx });
		}
		for (auto& p : cidx[i]) {
			int col = p.first, idx = p.second;
			for (Line& w : vcole[i][idx])
				V[vidx[i][idx]].push_back({ w.to, w.col, colsum[i][idx] - w.cost, idx });
		}
	}

	priority_queue<Q> pq;
	pq.push({ 1, 0 }); dst[1] = 0;
	while (!pq.empty()) {
		Q top = pq.top(); pq.pop();

		if (top.pos == n) break;

		for (Line& w : V[top.pos]) {
			ll& ret = dst[w.to];
			if (top.pos <= n) {
				if (w.to > n) {
					if (ret > top.cost) {
						ret = top.cost;
						pq.push({ w.to, ret });
					}
				}
				else {
					int idx = w.cc;
					if (colcnt[top.pos][idx] == 1) {
						if (ret > top.cost) {
							ret = top.cost;
							pq.push({ w.to, ret });
						}
					}
					else {
						if (ret > top.cost + w.cost) {
							ret = top.cost + w.cost;
							pq.push({ w.to, ret });
						}
						if (ret > top.cost + colsum[top.pos][idx] - w.cost) {
							ret = top.cost + colsum[top.pos][idx] - w.cost;
							pq.push({ w.to, ret });
						}
					}
				}
			}
			else {
				if (ret > top.cost + w.cost) {
					ret = top.cost + w.cost;
					pq.push({ w.to, ret });
				}
			}
		}
	}

	cout << (dst[n] == 1e18 ? -1 : dst[n]) << "\n";

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:8: warning: unused variable 'col' [-Wunused-variable]
   78 |    int col = p.first, idx = p.second;
      |        ^~~

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