Submission #379513

#	Time	Username	Problem	Language	Result	Execution time	Memory
379513		peijar	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	30 ms	4460 KiB

ho_t4

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

struct Arete
{
	int from, to, cost, costFlip;
};

const int MAXN = 200;
const int INF = 1e18;

vector<int> adj[MAXN];
vector<int> adjRev[MAXN];
vector<Arete> aretes;
int nbSommets, nbAretes;

pair<vector<int>, vector<int>> dijsktra(int from, bool flip=false)
{
	priority_queue<pair<int, int>> pq;
	pq.push({0, from});
	vector<int> distance(nbSommets, INF);
	vector<int> pred(nbSommets, -1);
	distance[from] = 0;
	while (!pq.empty())
	{
		auto [curDis, iNoeud] = pq.top(); pq.pop();
		curDis = -curDis;
		if (curDis > distance[iNoeud])
			continue;
		for (auto iArete : (flip ? adjRev[iNoeud] : adj[iNoeud]))
		{
			int iFrere = flip ? aretes[iArete].from : aretes[iArete].to;
			int nxtDis = curDis + aretes[iArete].cost;
			if (nxtDis < distance[iFrere])
			{
				pq.push({-nxtDis, iFrere});
				pred[iFrere] = iArete;
				distance[iFrere] = nxtDis;
			}
		}
	}
	return make_pair(distance, pred);
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> nbSommets >> nbAretes;
	aretes.resize(nbAretes);
	for (auto &[from, to, cost, costFlip] : aretes)
	{
		cin >> from >> to >> cost >> costFlip;
		--from, --to;
	}
	for (int iArete = 0; iArete < nbAretes; ++iArete) 
	{
		adj[aretes[iArete].from].push_back(iArete);
		adjRev[aretes[iArete].to].push_back(iArete);
	}

	auto [distances0, pred0] = dijsktra(0);
	auto [distances0Rev, pred0Rev] = dijsktra(0, 1);
	auto [distances1Rev, pred1Rev] = dijsktra(nbSommets-1, 1);
	auto [distances1, pred1] = dijsktra(nbSommets-1);
	/*for (auto v : distances0)
		cout << (v==INF?-1:v) << ' ';
	cout << endl;
	for (auto v : distances0Rev)
		cout << (v==INF?-1:v) << ' ';
	cout << endl;
	for (auto v : distances1)
		cout << (v==INF?-1:v) << ' ';
	cout << endl;
	for (auto v : distances1Rev)
		cout << (v==INF?-1:v) << ' ';
	cout << endl;*/

	int curSol = distances0[nbSommets-1] + distances1[0];
	curSol = min(curSol, INF);
	vector<bool> aretesPrise(nbAretes);

	if (distances0[nbSommets-1] != INF)
	{
		int cur = nbSommets-1;
		while (cur)
		{
			assert(pred0[cur] != -1);
			aretesPrise[pred0[cur]] = true;
			cur = aretes[pred0[cur]].from;
		}
	}

	if (distances1[0] != INF)
	{
		int cur = 0;
		while (cur != nbSommets-1)
		{
			assert(pred1[cur] != -1);
			aretesPrise[pred1[cur]] = true;
			cur = aretes[pred1[cur]].from;
		}
	}
	
	for (int iArete = 0; iArete < nbAretes; ++iArete) 
		if (!aretesPrise[iArete])
		{
			int dis0 = min(distances0[nbSommets-1],
					distances0[aretes[iArete].to] + distances1Rev[aretes[iArete].from]
					+ aretes[iArete].cost);
			int dis1 = min(distances1[0],
					distances1[aretes[iArete].to] + distances0Rev[aretes[iArete].from]
					+ aretes[iArete].cost);
			curSol = min(curSol, dis0 + dis1 + aretes[iArete].costFlip);
		}

	for (int iArete = 0; iArete < nbAretes; ++iArete) 
		if (aretesPrise[iArete])
		{
			int iFrom = aretes[iArete].from;
			int iTo = aretes[iArete].to;
			int posFrom = lower_bound(adj[iFrom].begin(), adj[iFrom].end(), iArete)
				- adj[iFrom].begin();
			int posTo = lower_bound(adjRev[iTo].begin(), adjRev[iTo].end(), iArete)
				- adjRev[iTo].begin();
			swap(aretes[iArete].from, aretes[iArete].to);
			swap(adj[iFrom][posFrom], adj[iFrom].back());
			swap(adjRev[iTo][posTo], adj[iTo].back());
			adj[iFrom].pop_back();
			adjRev[iTo].pop_back();
			adjRev[iFrom].push_back(iArete);
			adj[iTo].push_back(iArete);

			auto [dis0, p0] = dijsktra(0);
			auto [dis1, p1]= dijsktra(nbSommets-1);

			curSol = min(curSol, dis0[nbSommets-1] + dis1[0] + aretes[iArete].costFlip);

			adj[iTo].pop_back();
			adjRev[iFrom].pop_back();
			adj[iFrom].push_back(iArete);
			adjRev[iTo].push_back(iArete);
			swap(adj[iFrom][posFrom], adj[iFrom].back());
			swap(adjRev[iTo][posTo], adj[iTo].back());
			swap(aretes[iArete].from, aretes[iArete].to);
		}

	if (curSol == INF)
		curSol = -1;
	cout << curSol << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63