Submission #379548

#	Time	Username	Problem	Language	Result	Execution time	Memory
379548		peijar	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	181 ms	3804 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];
int matAdj[MAXN][MAXN];
vector<Arete> aretes;
int nbSommets, nbAretes;

// O(M log N)

pair<vector<int>, vector<int>> dijsktra(int from, bool flip=false)
{
	priority_queue<pair<int, int>> pq;
	pq.push({0, from});
	vector<int> distances, pred;
	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(move(distances), move(pred));
}

int disjk(int from, int to)
{
	vector<bool> vu(nbSommets);
	priority_queue<pair<int, int>> pq;
	pq.push({0, from});
	vector<int> dis(nbSommets, INF);
	dis[from] = 0;
	for (int iter(0); iter < nbSommets; ++iter)
	{
		int iBest(-1);
		for (int iNoeud(0); iNoeud < nbSommets; ++iNoeud)
			if (!vu[iNoeud] and (iBest == -1 or dis[iBest] > dis[iNoeud]))
				iBest = iNoeud;
		int curDis = dis[iBest];
		int iNoeud = iBest;
		if (iNoeud == to) return curDis;
		vu[iNoeud] = true;
		for (int iFrere(0); iFrere < nbSommets; ++iFrere)
			dis[iFrere] = min(dis[iFrere], curDis + matAdj[iNoeud][iFrere]);
	}
	return INF;
}

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 [distances1, pred1] = dijsktra(nbSommets-1);
	auto [distances1Rev, pred1Rev] = dijsktra(nbSommets-1, 1);
	int curSol = INF;
	if (distances0[nbSommets-1] < INF and distances1[0] < INF)
		curSol = distances0[nbSommets-1] + distances1[0];
	vector<bool> aretesPrise(nbAretes);

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

	if (distances1[0] != INF)
	{
		int cur = 0;
		while (cur != nbSommets-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 = distances0[nbSommets-1];
			int dis1 = distances1[0];;
			int iTo = aretes[iArete].to;
			int iFrom = aretes[iArete].from;
			if (distances0[iTo] < INF and distances1Rev[iFrom] < INF)
				dis0 = min(dis0, 
						distances0[aretes[iArete].to] + distances1Rev[aretes[iArete].from]
						+ aretes[iArete].cost);
			if (distances1[iTo] < INF and distances0Rev[iFrom] < INF)
				dis1 = min(dis1, 
						distances1[aretes[iArete].to] + distances0Rev[aretes[iArete].from]
						+ aretes[iArete].cost);
			if (dis0 < INF and dis1 < INF)
				curSol = min(curSol, dis0 + dis1 + aretes[iArete].costFlip);
		}

	// If we 

	for (int iArete = 0; iArete < nbAretes; ++iArete) 
		if (aretesPrise[iArete])
		{
			for (int i = 0; i < nbSommets; ++i) 
				for (int j = 0; j < nbSommets; ++j) 
					matAdj[i][j] = INF;
			for (int iArete2 = 0; iArete2 < nbAretes; ++iArete2)
			{
				int u = aretes[iArete2].from;
				int v = aretes[iArete2].to;
				if (iArete2 == iArete)
					swap(u, v);
				matAdj[u][v] = min(matAdj[u][v], aretes[iArete2].cost);
			}
			curSol = min(curSol, aretes[iArete].costFlip + disjk(0, nbSommets-1) + disjk(nbSommets-1, 0));
		}

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

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