Submission #828495

#	Time	Username	Problem	Language	Result	Execution time	Memory
828495		denniskim	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	321 ms	19088 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll U, V, C, D;
};

ll n, m;
vector<pll> vec[210], yuk[210];
vector< pair<ll, pll> > vec2[210];
gujo tmp;
ll Jdist[210][210][2];
ll Ydist[210][210][2];
multiset<pll> Jst[210][2], Yst[210][2];
ll ans = INF;

void dijksta1(ll X)
{
	priority_queue<pll> pq;
	
	for(ll i = 1 ; i <= n ; i++)
		Jdist[X][i][0] = Jdist[X][i][1] = INF;
	
	Jdist[X][1][0] = 0;
	pq.push({0, 1});
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		for(auto &i : vec[qq.se])
		{
			if(i.fi == X)
				continue;
			
			if(Jdist[X][i.fi][0] > Jdist[X][qq.se][0] + i.se)
			{
				Jdist[X][i.fi][0] = Jdist[X][qq.se][0] + i.se;
				pq.push({-Jdist[X][i.fi][0], i.fi});
			}
		}
	}
	
	Jdist[X][n][1] = 0;
	pq.push({0, n});
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		for(auto &i : vec[qq.se])
		{
			if(i.fi == X)
				continue;
			
			if(Jdist[X][i.fi][1] > Jdist[X][qq.se][1] + i.se)
			{
				Jdist[X][i.fi][1] = Jdist[X][qq.se][1] + i.se;
				pq.push({-Jdist[X][i.fi][1], i.fi});
			}
		}
	}
}

void dijksta2(ll X)
{
	priority_queue<pll> pq;
	
	for(ll i = 1 ; i <= n ; i++)
		Ydist[X][i][0] = Ydist[X][i][1] = INF;
	
	Ydist[X][1][0] = 0;
	pq.push({0, 1});
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		for(auto &i : yuk[qq.se])
		{
			if(i.fi == X)
				continue;
			
			if(Ydist[X][i.fi][0] > Ydist[X][qq.se][0] + i.se)
			{
				Ydist[X][i.fi][0] = Ydist[X][qq.se][0] + i.se;
				pq.push({-Ydist[X][i.fi][0], i.fi});
			}
		}
	}
	
	Ydist[X][n][1] = 0;
	pq.push({0, n});
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		for(auto &i : yuk[qq.se])
		{
			if(i.fi == X)
				continue;
			
			if(Ydist[X][i.fi][1] > Ydist[X][qq.se][1] + i.se)
			{
				Ydist[X][i.fi][1] = Ydist[X][qq.se][1] + i.se;
				pq.push({-Ydist[X][i.fi][1], i.fi});
			}
		}
	}
}

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		cin >> tmp.U >> tmp.V >> tmp.C >> tmp.D;
		
		vec[tmp.U].push_back({tmp.V, tmp.C});
		yuk[tmp.V].push_back({tmp.U, tmp.C});
		vec2[tmp.U].push_back({tmp.V, {tmp.C, tmp.D}});
	}
	
	dijksta1(0);
	dijksta2(0);
	
	for(ll i = 2 ; i < n ; i++)
	{
		dijksta1(i);
		dijksta2(i);
	}
	
	ans = min(ans, Jdist[0][n][0] + Jdist[0][1][1]);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(auto &j : yuk[i])
		{
			Jst[i][0].insert({Jdist[0][j.fi][0] + j.se, j.fi});
			Jst[i][1].insert({Jdist[0][j.fi][1] + j.se, j.fi});
		}
		
		for(auto &j : vec[i])
		{
			Yst[i][0].insert({Ydist[0][j.fi][0] + j.se, j.fi});
			Yst[i][1].insert({Ydist[0][j.fi][1] + j.se, j.fi});
		}
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(auto &j : vec2[i]) //i -> j
		{
			ll cost1 = INF, cost2 = INF;
			
			for(auto &k : vec2[i])
			{
				if(j == k)
					continue;
				
				cost1 = min(cost1, Jdist[0][i][0] + k.se.fi + Ydist[0][k.fi][1]);
			}
			
			if(i != 1 && i != n)
				cost1 = min(cost1, Jdist[i][n][0]);
			
			auto p1 = Jst[j.fi][0].begin();
			auto p2 = Yst[i][1].begin();
			
			if((*p1).se == i)
				p1++;
			
			if((*p2).se == j.fi)
				p2++;
			
			if(p1 != Jst[j.fi][0].end() && p2 != Yst[i][1].begin())
				cost1 = min(cost1, (*p1).fi + j.se.fi + (*p2).fi);
			
			if(i == n)
				cost1 = min(cost1, j.se.fi + (*p1).fi);
			
			if(j.fi == 1)
				cost1 = min(cost1, j.se.fi + (*p2).fi);
			
			if(i == n && j.fi == 1)
				cost1 = min(cost1, j.se.fi);
			
			for(auto &k : vec2[i])
			{
				if(j == k)
					continue;
				
				cost2 = min(cost2, Jdist[0][i][1] + k.se.fi + Ydist[0][k.fi][0]);
			}
			
			if(i != 1 && i != n)
				cost2 = min(cost2, Jdist[i][1][1]);
			
			p1 = Jst[j.fi][1].begin();
			p2 = Yst[i][0].begin();
			
			if((*p1).se == i)
				p1++;
			
			if((*p2).se == j.fi)
				p2++;
			
			if(p1 != Jst[j.fi][1].end() && p2 != Yst[i][0].begin())
				cost2 = min(cost2, (*p1).fi + j.se.fi + (*p2).fi);
			
			if(i == 1)
				cost2 = min(cost2, j.se.fi + (*p1).fi);
			
			if(j.fi == n)
				cost2 = min(cost2, j.se.fi + (*p2).fi);
			
			if(i == 1 && j.fi == n)
				cost2 = min(cost2, j.se.fi);
			
			ans = min(ans, cost1 + cost2 + j.se.se);
		}
	}
	
	if(ans >= INF)
		cout << -1;
	else
		cout << ans;
	
	return 0;
}

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