oj.uz

Submission #828544

# Submission time Handle Problem Language Result Execution time Memory
828544 2023-08-17T10:58:42 Z denniskim Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 320 ms 18484 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++)
	{
		ll idx1 = 0;
		
		for(auto &j : vec2[i]) //i -> j
		{
			ll cost1 = INF, cost2 = INF, idx2 = 0;
			idx1++;
			
			for(auto &k : vec2[i])
			{
				idx2++;
				
				if(idx1 == idx2)
					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);
			}
			
			idx2 = 0;
			
			for(auto &k : vec2[i])
			{
				idx2++;
				
				if(idx1 == idx2)
					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 1984 KB Output is correct
4 Correct 20 ms 2016 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 700 KB Output is correct
10 Correct 28 ms 1904 KB Output is correct
11 Correct 27 ms 2040 KB Output is correct
12 Incorrect 27 ms 1984 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 320 ms 17940 KB Output is correct
2 Correct 308 ms 18116 KB Output is correct
3 Correct 318 ms 18028 KB Output is correct
4 Correct 22 ms 2320 KB Output is correct
5 Correct 11 ms 1944 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 151 ms 18324 KB Output is correct
10 Correct 151 ms 18316 KB Output is correct
11 Correct 259 ms 18032 KB Output is correct
12 Correct 251 ms 17952 KB Output is correct
13 Correct 244 ms 18124 KB Output is correct
14 Correct 250 ms 18484 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 94 ms 14232 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 125 ms 17760 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 91 ms 18408 KB Output is correct
9 Correct 90 ms 18356 KB Output is correct
10 Incorrect 108 ms 17868 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 1984 KB Output is correct
4 Correct 20 ms 2016 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 700 KB Output is correct
10 Correct 28 ms 1904 KB Output is correct
11 Correct 27 ms 2040 KB Output is correct
12 Incorrect 27 ms 1984 KB Output isn't correct
13 Halted 0 ms 0 KB -