oj.uz

Submission #828547

# Submission time Handle Problem Language Result Execution time Memory
828547 2023-08-17T11:00:06 Z denniskim Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 320 ms 18492 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 / 2
#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 14 ms 2068 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 22 ms 1964 KB Output is correct
4 Correct 20 ms 1980 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 1 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 28 ms 2004 KB Output is correct
11 Correct 29 ms 1996 KB Output is correct
12 Incorrect 28 ms 1992 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 17972 KB Output is correct
2 Correct 305 ms 17996 KB Output is correct
3 Correct 311 ms 17984 KB Output is correct
4 Correct 25 ms 2312 KB Output is correct
5 Correct 12 ms 2028 KB Output is correct
6 Correct 4 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 18312 KB Output is correct
10 Correct 150 ms 18324 KB Output is correct
11 Correct 247 ms 17892 KB Output is correct
12 Correct 256 ms 17960 KB Output is correct
13 Correct 246 ms 18108 KB Output is correct
14 Correct 260 ms 18480 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 91 ms 14248 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 129 ms 17780 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 97 ms 18492 KB Output is correct
9 Correct 89 ms 18352 KB Output is correct
10 Incorrect 108 ms 17936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2068 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 22 ms 1964 KB Output is correct
4 Correct 20 ms 1980 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 1 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 28 ms 2004 KB Output is correct
11 Correct 29 ms 1996 KB Output is correct
12 Incorrect 28 ms 1992 KB Output isn't correct
13 Halted 0 ms 0 KB -