oj.uz

Submission #380388

# Submission time Handle Problem Language Result Execution time Memory
380388 2021-03-21T11:15:37 Z peijar Robot (JOI21_ho_t4) C++17
0 / 100
 151 ms 24808 KB 
#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(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[curDis] < 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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 1 ms 620 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 24808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 1 ms 620 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -