oj.uz

답안 #828562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828562 2023-08-17T11:17:38 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 / 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 19 ms 1984 KB Output is correct
4 Correct 20 ms 2004 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 2 ms 1668 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 1944 KB Output is correct
11 Correct 31 ms 2004 KB Output is correct
12 Incorrect 28 ms 1920 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 18076 KB Output is correct
2 Correct 309 ms 18068 KB Output is correct
3 Correct 310 ms 18060 KB Output is correct
4 Correct 21 ms 2260 KB Output is correct
5 Correct 13 ms 2024 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 152 ms 18236 KB Output is correct
10 Correct 151 ms 18388 KB Output is correct
11 Correct 244 ms 17924 KB Output is correct
12 Correct 252 ms 17904 KB Output is correct
13 Correct 251 ms 18128 KB Output is correct
14 Correct 253 ms 18484 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1972 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 94 ms 14304 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 121 ms 17796 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 95 ms 18408 KB Output is correct
9 Correct 96 ms 18352 KB Output is correct
10 Incorrect 109 ms 18004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 19 ms 1984 KB Output is correct
4 Correct 20 ms 2004 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 2 ms 1668 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 1944 KB Output is correct
11 Correct 31 ms 2004 KB Output is correct
12 Incorrect 28 ms 1920 KB Output isn't correct
13 Halted 0 ms 0 KB -