Robot

Explicación

Lema: Siempre podemos recolorear una arista $(u, v)$ de modo que su color sea distinto de los de las otras aristas incidentes a $u$ y $v$.

Demostración: Si quitamos $(u, v)$, entonces hay a lo sumo $M - 1$ aristas incidentes a $u$ y $v$. Como hay $M$ colores en total, debe existir algún color tal que ninguna de esas aristas lo tenga (por el principio del palomar). Por lo tanto, simplemente podemos recolorear $(u, v)$ a ese color.

Esto significa que podemos definir el costo de recorrer una arista como:

Puede ser tentador usar el algoritmo de Dijkstra en este punto, pero eso lamentablemente dará una respuesta incorrecta. Consideremos lo siguiente:

• El robot recorre el camino $u \rightarrow v \rightarrow w$.
• $(u, v)$ y $(v, w)$ tienen el mismo color.
• Es óptimo recolorear $(u, v)$ al ir $u \rightarrow v$, pero es óptimo recolorear los vecinos del mismo color de $(v, w)$ al ir $v \rightarrow w$.

En este caso, usar el algoritmo de Dijkstra de forma naive contará el costo de recolorear $(u, v)$ dos veces en nuestra respuesta.

Para enmendar esto, definamos dos arreglos de DP en lugar de solo uno:

• $\texttt{dp1}[i]$ es el costo mínimo para llegar al nodo $i$.
• $\texttt{dp2}[i][c]$ es el costo mínimo para llegar al nodo $i$ si:
  • El robot acaba de recorrer una arista de color $c$ para llegar al nodo $i$.
  • Se supone que hemos recoloreado esa arista, pero aún no lo hemos hecho.
  • El robot definitivamente saldrá del nodo $i$ por otra arista de color $c$ y recolorearemos todos sus vecinos del mismo color.

Luego podemos usar el algoritmo de Dijkstra y algo de análisis por casos para resolver este problema en tiempo amortizado $\mathcal O((N + M) \log N)$.

Implementación

Complejidad temporal: $\mathcal O((N + M) \log N)$

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const ll INF = 1e18;
 
struct Edge {
	int to, c;
	ll p;
};
 
map<int, vector<Edge>> graph[100001];
ll dp[100001];
map<int, ll> dp2[100001], psum[100001];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		ll p;
		cin >> u >> v >> c >> p;
		graph[u][c].push_back({v, c, p});
		graph[v][c].push_back({u, c, p});
		psum[u][c] += p;
		psum[v][c] += p;
	}
 
	memset(dp, 0x3f, sizeof dp);
	dp[1] = 0;
	priority_queue<tuple<ll, int, int>> pq;
	pq.push({0, 1, 0});
	while (pq.size()) {
		ll cost;
		int node, c;
		tie(cost, node, c) = pq.top();
		pq.pop();
 
		if (c) {
			if (dp2[node][c] != -cost) continue;
			for (Edge i : graph[node][c]) {
				// No podemos voltear i en este caso
				ll case1 = psum[node][c] - i.p;
				if (case1 - cost < dp[i.to]) {
					dp[i.to] = case1 - cost;
					pq.push({-dp[i.to], i.to, 0});
				}
			}
		} else {
			if (dp[node] != -cost) continue;
			for (auto &i : graph[node]) {
				for (Edge j : i.second) {
					// Caso 1: no volteamos j
					ll case1 = psum[node][j.c] - j.p - cost;
					if (case1 < dp[j.to]) {
						dp[j.to] = case1;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Caso 2: volteamos j pero no otra arista del mismo color
					ll case2 = j.p - cost;
					if (case2 < dp[j.to]) {
						dp[j.to] = case2;
						pq.push({-dp[j.to], j.to, 0});
					}
					// Caso 3: volteamos j y otra arista del mismo color
					ll case3 = -cost;
					if (!dp2[j.to].count(j.c) || case3 < dp2[j.to][j.c]) {
						dp2[j.to][j.c] = case3;
						pq.push({-dp2[j.to][j.c], j.to, j.c});
					}
				}
			}
		}
	}
	cout << (dp[n] > INF ? -1 : dp[n]);
	return 0;
}