oj.uz

Submission #828539

# Submission time Handle Problem Language Result Execution time Memory
828539 2023-08-17T10:51:58 Z denniskim Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 331 ms 19212 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 != Jst[j.fi][0].end() && p2 != Yst[i][1].end())
			{
				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(p1 != Jst[j.fi][0].end() && i == n)
					cost1 = min(cost1, j.se.fi + (*p1).fi);
				
				if(p2 != Yst[i][1].end() && 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 != Jst[j.fi][1].end() && p2 != Yst[i][0].end())
			{
				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(p1 != Jst[j.fi][1].end() && i == 1)
					cost2 = min(cost2, j.se.fi + (*p1).fi);
				
				if(p2 != Yst[i][0].end() && 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 1 ms 1748 KB Output is correct
3 Correct 19 ms 2032 KB Output is correct
4 Correct 20 ms 1920 KB Output is correct
5 Correct 3 ms 912 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 4 ms 724 KB Output is correct
10 Correct 28 ms 1996 KB Output is correct
11 Correct 32 ms 2064 KB Output is correct
12 Incorrect 27 ms 2004 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 331 ms 18140 KB Output is correct
2 Correct 321 ms 18248 KB Output is correct
3 Correct 327 ms 18464 KB Output is correct
4 Correct 23 ms 2388 KB Output is correct
5 Correct 11 ms 2004 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 340 KB Output is correct
9 Correct 157 ms 18688 KB Output is correct
10 Correct 156 ms 18696 KB Output is correct
11 Correct 263 ms 18336 KB Output is correct
12 Correct 254 ms 18300 KB Output is correct
13 Correct 271 ms 18456 KB Output is correct
14 Correct 266 ms 18856 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1928 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 99 ms 15164 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 124 ms 18708 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 107 ms 19208 KB Output is correct
9 Correct 95 ms 19212 KB Output is correct
10 Incorrect 114 ms 18944 KB Output isn't correct
11 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 1 ms 1748 KB Output is correct
3 Correct 19 ms 2032 KB Output is correct
4 Correct 20 ms 1920 KB Output is correct
5 Correct 3 ms 912 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 4 ms 724 KB Output is correct
10 Correct 28 ms 1996 KB Output is correct
11 Correct 32 ms 2064 KB Output is correct
12 Incorrect 27 ms 2004 KB Output isn't correct
13 Halted 0 ms 0 KB -