Submission #388739

#	Time	Username	Problem	Language	Result	Execution time	Memory
388739		Vlatko	Robot (JOI21_ho_t4)	C++17	0 / 100	142 ms	16236 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll inf = 1e18;
const int N = 100100;
const int M = 200100;

int n, m;
vector<tuple<int, int, int>> adj[N];

int last[M]; // last node that had an edge with this color
int ccnt[M]; // for current node, how many edges with this color
ll csum[M]; // for current node, sum of weights of edges with this color

void process_color(int c, int w, int u) {
	if (last[c] != u) {
		last[c] = u;
		ccnt[c] = 1;
		csum[c] = w;
	} else {
		ccnt[c] += 1;
		csum[c] += w;
	}
}

ll dijkstra(int src) {
	using pii = pair<int, int>;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	static ll dist[N];
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
	}
	for (int i = 0; i < m; ++i) {
		last[i] = -1;
	}
	dist[src] = 0;
	pq.emplace(0, src);
	while (!pq.empty()) {
		ll cur_dist;
		int u;
		tie(cur_dist, u) = pq.top();
		pq.pop();
		if (cur_dist != dist[u]) continue;
		for (auto& to : adj[u]) {
			int c, w;
			tie(ignore, c, w) = to;
			process_color(c, w, u);
		}
		for (auto& to : adj[u]) {
			int v, c, w;
			tie(v, c, w) = to;
			// in case there is more than 1 edge with color c:
			// either change the color of this edge (cost: w)
			// or all others (cost: csum[c] - w)
			// since 1 <= c <= M and degree[u] < M,
			// we can always change the edges to some color
			// that won't interfere in future operations
			// also, we can change edges like this because
			// all edges adjacent to u won't be crossed ever again
			ll alt = dist[u] + min((ll)w, csum[c]-w);
			if (alt < dist[v]) {
				dist[v] = alt;
				pq.emplace(alt, v);
			}
		}
	}
	return dist[n] == inf ? -1 : dist[n];
}

ll solve_star(int center) {
	// center has a degree of M
	// special measures must be taken
	for (int c = 0; c < m; ++c) {
		last[c] = -1;
	}
	int c1, cn;
	ll w1, wn;
	for (auto& to : adj[center]) {
		int v, c, w;
		tie(v, c, w) = to;
		process_color(c, w, center);
		if (v == 1) {
			w1 = w;
			c1 = c;
		} else if (v == n) {
			wn = w;
			cn = w;
		}
	}
	if (center == 1) {
		return min(wn, csum[cn]-wn);
	} else if (center == n) {
		return min(w1, csum[c1]-w1);
	} else if (c1 == cn) {
		return min(w1+wn, min(csum[c1]-w1, csum[c1]-wn));
	} else {
		return min(w1, csum[c1]-w1) + min(wn, csum[cn]-wn);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c, w;
		cin >> a >> b >> c >> w;
		adj[a].emplace_back(b, c, w);
		adj[b].emplace_back(a, c, w);
	}
	for (int u = 1; u <= n; ++u) {
		if (adj[u].size() == m) {
			cout << solve_star(u) << '\n';
			return 0;
		}
	}
	cout << dijkstra(1) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:113:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |   if (adj[u].size() == m) {
      |       ~~~~~~~~~~~~~~^~~~
Main.cpp: In function 'll solve_star(int)':
Main.cpp:79:9: warning: 'wn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  ll w1, wn;
      |         ^~
Main.cpp:79:5: warning: 'w1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  ll w1, wn;
      |     ^~
Main.cpp:99:48: warning: 'cn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |   return min(w1, csum[c1]-w1) + min(wn, csum[cn]-wn);
      |                                         ~~~~~~~^
Main.cpp:78:6: warning: 'c1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |  int c1, cn;
      |      ^~

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