oj.uz

Submission #828515

# Submission time Handle Problem Language Result Execution time Memory
828515 2023-08-17T10:41:08 Z denniskim Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 323 ms 19580 KB 
#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(p1 != Jst[j.fi][0].end() && (*p1).se == i)
					p1--;
			}
			
			if((*p2).se == j.fi)
			{
				p2++;
				
				if(p2 != Yst[i][1].end() && (*p2).se == i)
					p2--;
			}
			
			if(p1 != Jst[j.fi][0].end() && p2 != Yst[i][1].end())
				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(p1 != Jst[j.fi][1].end() && (*p1).se == i)
					p1--;
			}
			
			if((*p2).se == j.fi)
			{
				p2++;
				
				if(p2 != Yst[i][0].end() && (*p2).se == j.fi)
					p2--;
			}
			
			if(p1 != Jst[j.fi][1].end() && p2 != Yst[i][0].end())
				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 - 10000000000)
		cout << -1;
	else
		cout << ans;
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 19 ms 2020 KB Output is correct
4 Correct 20 ms 1956 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 29 ms 1940 KB Output is correct
11 Correct 27 ms 1996 KB Output is correct
12 Incorrect 27 ms 1952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 17952 KB Output is correct
2 Correct 317 ms 18120 KB Output is correct
3 Correct 320 ms 19232 KB Output is correct
4 Correct 22 ms 2308 KB Output is correct
5 Correct 11 ms 2008 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 0 ms 388 KB Output is correct
9 Correct 161 ms 19428 KB Output is correct
10 Correct 156 ms 19580 KB Output is correct
11 Correct 260 ms 19108 KB Output is correct
12 Correct 258 ms 19116 KB Output is correct
13 Correct 267 ms 19252 KB Output is correct
14 Correct 262 ms 19532 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1972 KB Output is correct
2 Incorrect 2 ms 1748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 19 ms 2020 KB Output is correct
4 Correct 20 ms 1956 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 29 ms 1940 KB Output is correct
11 Correct 27 ms 1996 KB Output is correct
12 Incorrect 27 ms 1952 KB Output isn't correct
13 Halted 0 ms 0 KB -