Submission #380280

#	Time	Username	Problem	Language	Result	Execution time	Memory
380280		peijar	Robot (JOI21_ho_t4)	C++17	34 / 100	3070 ms	50892 KiB

Main

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

const int INF = 1e18;

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbSommets, nbAretes;
	cin >> nbSommets >> nbAretes;

	vector<vector<tuple<int, int, int>>> adj(nbSommets+1);
	vector<vector<int>> couleursAdjacentes(nbSommets+1);
	vector<vector<int>> totCostCol(nbSommets+1);

	for (int iArete = 0; iArete < nbAretes; ++iArete) 
	{
		int iFrom, iTo, col, cost;
		cin >> iFrom >> iTo >> col >> cost;
		adj[iFrom].emplace_back(iTo, col, cost);
		adj[iTo].emplace_back(iFrom, col, cost);
		couleursAdjacentes[iFrom].push_back(col);
		couleursAdjacentes[iTo].push_back(col);
	}

	auto getIdCol = [&](int iSommet, int iCol)
	{
		return lower_bound(couleursAdjacentes[iSommet].begin(), couleursAdjacentes[iSommet].end(), iCol) - couleursAdjacentes[iSommet].begin();
	};

	for (int iSommets = 1; iSommets <= nbSommets; ++iSommets) 
	{
		sort(couleursAdjacentes[iSommets].begin(), couleursAdjacentes[iSommets].end());
		couleursAdjacentes[iSommets].resize(unique(couleursAdjacentes[iSommets].begin(), couleursAdjacentes[iSommets].end())-couleursAdjacentes[iSommets].begin());
		totCostCol[iSommets].resize(couleursAdjacentes[iSommets].size());
		for (auto [to, col, cost] : adj[iSommets])
			totCostCol[iSommets][getIdCol(iSommets, col)] += cost;
		sort(adj[iSommets].begin(), adj[iSommets].end());
	}

	vector<vector<int>> dis(nbSommets+1);

	for (int iSommets(1); iSommets <= nbSommets; ++iSommets)
		dis[iSommets].assign(1 + adj[iSommets].size(), INF);

	auto getIdAdj = [&](int iSommet, int iFrere)
	{
		return 1 + (lower_bound(adj[iFrere].begin(), adj[iFrere].end(), make_tuple(iSommet, 0, 0)) - adj[iFrere].begin());
	};

	dis[1][0] = 0;
	priority_queue<tuple<int,int, int>> pq;
	pq.emplace(0, 1, 0);

	while (!pq.empty())
	{
		auto [curCost, iSommet, iFrom] = pq.top(); pq.pop();
		curCost = -curCost;
		if (dis[iSommet][iFrom] > curCost) continue;
		iFrom--;

		for (auto [iFrere, iCol, coutChange] : adj[iSommet])
		{
			
			// Soit on change la couleur :
			int idFrere = getIdAdj(iSommet, iFrere);
			assert(get<0>(adj[iFrere][idFrere-1]) == iSommet);
			if (dis[iFrere][idFrere] > curCost + coutChange)
			{
				dis[iFrere][idFrere] = curCost + coutChange;
				pq.emplace(-dis[iFrere][idFrere], iFrere, idFrere);
			}

			// Soit on change toutes les autres :
			int nxtCost = curCost + totCostCol[iSommet][getIdCol(iSommet, iCol)] - coutChange;
			if (iFrom != -1 and get<1>(adj[iSommet][iFrom]) == iCol)
				nxtCost -= get<2>(adj[iSommet][iFrom]);
			if (dis[iFrere][0] > nxtCost)
			{
				dis[iFrere][0] = nxtCost;
				pq.emplace(-nxtCost, iFrere, 0);
			}
		}
	}

	int sol = INF;
	for (auto v : dis[nbSommets])
		sol = min(sol, v);
	if (sol == INF) sol = -1;
	cout << sol << endl;

}

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