Submission #831161

#	Time	Username	Problem	Language	Result	Execution time	Memory
831161		denniskim	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	199 ms	10160 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 0x3f3f3f3f3f3f3f3 / 100
#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 V, C, D, num;
};

ll n, m;
ll all, bll, cll, dll;
vector< pair<pll, pll> > edg;
vector<gujo> vec[210], yuk[210];
ll ans[50010];
ll dist[210][2];
ll dist2[50010][210][2];
ll bk[210][2], bk2[210][2];
ll chk[210], chk2[50010];
ll ans2 = INF, ans3;

void dijkstra(ll X)
{
	for(ll i = 1 ; i <= n ; i++)
		dist[i][0] = INF, bk[i][0] = bk2[i][0] = chk[i] = 0;
	
	dist[1][0] = 0;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		ll minn = INF, w = -1;
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(chk[j])
				continue;
			
			if(minn > dist[j][0])
			{
				minn = dist[j][0];
				w = j;
			}
		}
		
		if(w == -1)
			break;
		
		chk[w] = 1;
		
		for(auto &j : vec[w])
		{
			if(j.num == X)
				continue;
			
			if(dist[j.V][0] > dist[w][0] + j.C)
			{
				dist[j.V][0] = dist[w][0] + j.C;
				bk[j.V][0] = w;
				bk2[j.V][0] = j.num;
			}
		}
	}
	
	for(ll i = 1 ; i <= n ; i++)
		dist[i][1] = INF, bk[i][1] = bk2[i][1] = chk[i] = 0;
	
	dist[n][1] = 0;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		ll minn = INF, w = -1;
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(chk[j])
				continue;
			
			if(minn > dist[j][1])
			{
				minn = dist[j][1];
				w = j;
			}
		}
		
		if(w == -1)
			break;
		
		chk[w] = 1;
		
		for(auto &j : yuk[w])
		{
			if(j.num == X)
				continue;
			
			if(dist[j.V][1] > dist[w][1] + j.C)
			{
				dist[j.V][1] = dist[w][1] + j.C;
				bk[j.V][1] = w;
				bk2[j.V][1] = j.num;
			}
		}
	}
	
	for(ll i = 1 ; i <= n ; i++)
		dist2[X][i][0] = dist[i][0], dist2[X][i][1] = dist[i][1];
}

void solve(void)
{
	dijkstra(0);
	
	ans3 += dist2[0][n][0];
	
	vector<ll> path;
	
	for(ll i = n ; i > 0 ; i = bk[i][0])
		path.push_back(bk2[i][0]);
	
	for(ll i = 1 ; i <= m ; i++)
		chk2[i] = 0;
	
	for(auto &i : path)
	{
		dijkstra(i);
		chk2[i] = 1;
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(!chk2[i])
			ans[i] += min(dist2[0][n][0], dist2[0][edg[i - 1].fi.se][0] + dist2[0][edg[i - 1].fi.fi][1] + edg[i - 1].se.fi);
		else
			ans[i] += min(dist2[i][n][0], dist2[i][edg[i - 1].fi.se][0] + dist2[i][edg[i - 1].fi.fi][1] + edg[i - 1].se.fi);
	}
}

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		cin >> all >> bll >> cll >> dll;
		
		edg.push_back({{all, bll}, {cll, dll}});
		vec[all].push_back({bll, cll, dll, i});
		yuk[bll].push_back({all, cll, dll, i});
		ans[i] += dll;
	}
	
	solve();
	
	for(ll i = 1 ; i <= n ; i++)
	{
		vec[i].clear();
		yuk[i].clear();
	}
	
	ll cc = 0;
	
	for(auto &i : edg)
	{
		if(i.fi.fi == 1)
			i.fi.fi = n;
		else if(i.fi.fi == n)
			i.fi.fi = 1;
		
		if(i.fi.se == 1)
			i.fi.se = n;
		else if(i.fi.se == n)
			i.fi.se = 1;
		
		cc++;
		vec[i.fi.fi].push_back({i.fi.se, i.se.fi, i.se.se, cc});
		yuk[i.fi.se].push_back({i.fi.fi, i.se.fi, i.se.se, cc});
	}
	
	solve();
	
	for(ll i = 1 ; i <= m ; i++)
		ans2 = min(ans2, ans[i]);
	
	ans2 = min(ans2, ans3);
	
	if(ans2 >= INF / 10)
		cout << -1;
	else
		cout << ans2;
	
	return 0;
}

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