Submission #380390

#	Time	Username	Problem	Language	Result	Execution time	Memory
380390		peijar	Robot (JOI21_ho_t4)	C++17	100 / 100	459 ms	74388 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>>> aretesAdj(nbSommets+1);
	for (int iArete = 0; iArete < nbAretes; ++iArete) 
	{
		int u, v, iCol, cost;
		cin >> u >> v >> iCol >> cost;
		aretesAdj[u].emplace_back(iCol, v, cost);
		aretesAdj[v].emplace_back(iCol, u, cost);
	}

	int szAdj = nbSommets;
	vector<vector<pair<int, int>>> adj(nbSommets+1);
	for (int iSommet = 1; iSommet <= nbSommets; ++iSommet) 
	{
		sort(aretesAdj[iSommet].begin(), aretesAdj[iSommet].end());
		int deg = aretesAdj[iSommet].size();
		for (int iAdj(0); iAdj < deg;)
		{
			int iPos(iAdj);
			int col = get<0>(aretesAdj[iSommet][iAdj]);
			int totCost = 0;
			while (iPos < deg and get<0>(aretesAdj[iSommet][iPos]) == col)
				totCost += get<2>(aretesAdj[iSommet][iPos++]);
			adj.emplace_back();
			adj[iSommet].emplace_back(++szAdj, 0);
			for (int i(iAdj); i < iPos; ++i)
			{
				auto [icol, iFrere, cost] = aretesAdj[iSommet][i];
				adj[iSommet].emplace_back(iFrere, cost);
				adj[iFrere].emplace_back(szAdj, 0);
				adj[szAdj].emplace_back(iFrere, totCost - cost);
			}
			iAdj = iPos;
		}
	}
	vector<int> dis(1+adj.size(), INF);
	dis[0] = 0;
	priority_queue<pair<int, int>> pq;
	pq.emplace(0, 1);
	while (!pq.empty())
	{
		auto [curDis, iNoeud] = pq.top(); pq.pop();

		curDis = -curDis;
		if (dis[iNoeud] < curDis) continue;
		for (auto [iFrere, iCout] : adj[iNoeud])
			if (iCout + curDis < dis[iFrere])
			{
				dis[iFrere] = iCout + curDis;
				pq.emplace(-dis[iFrere], iFrere);
			}
	}
	int sol = dis[nbSommets];
	if (sol == INF) sol = -1;
	cout<< sol << endl;
}

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