제출 #379539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379539		peijar	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1098 ms	3436 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;

// O(M log N)

vector<int> distances, pred;

pair<vector<int>, vector<int>> dijsktra(int from, bool flip=false)
{
	priority_queue<pair<int, int>> pq;
	pq.push({0, from});
	distances.assign(nbSommets, INF);
	pred.assign(nbSommets, -1);
	distances[from] = 0;
	while (!pq.empty())
	{
		auto [curDis, iNoeud] = pq.top(); pq.pop();
		curDis = -curDis;
		if (curDis > distances[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 < distances[iFrere])
			{
				pq.push({-nxtDis, iFrere});
				pred[iFrere] = iArete;
				distances[iFrere] = nxtDis;
			}
		}
	}
	return make_pair(distances, 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 [distancess0, pred0] = dijsktra(0);
	auto [distancess0Rev, pred0Rev] = dijsktra(0, 1);
	auto [distancess1, pred1] = dijsktra(nbSommets-1);
	auto [distancess1Rev, pred1Rev] = dijsktra(nbSommets-1, 1);

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

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

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

	// O(NM log N)
	
	for (int iArete = 0; iArete < nbAretes; ++iArete) 
		if (!aretesPrise[iArete])
		{
			int dis0 = min(distancess0[nbSommets-1],
					distancess0[aretes[iArete].to] + distancess1Rev[aretes[iArete].from]
					+ aretes[iArete].cost);
			int dis1 = min(distancess1[0],
					distancess1[aretes[iArete].to] + distancess0Rev[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], adjRev[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], adjRev[iTo].back());
			swap(aretes[iArete].from, aretes[iArete].to);
		}

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

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