oj.uz

답안 #828541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828541 2023-08-17T10:53:58 Z denniskim Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 316 ms 18424 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 20 ms 1988 KB Output is correct
4 Correct 21 ms 1984 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 696 KB Output is correct
10 Correct 32 ms 1992 KB Output is correct
11 Correct 28 ms 2000 KB Output is correct
12 Incorrect 28 ms 1900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 18052 KB Output is correct
2 Correct 304 ms 18064 KB Output is correct
3 Correct 313 ms 17952 KB Output is correct
4 Correct 22 ms 2260 KB Output is correct
5 Correct 11 ms 1980 KB Output is correct
6 Correct 3 ms 1836 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 167 ms 18324 KB Output is correct
10 Correct 164 ms 18424 KB Output is correct
11 Correct 257 ms 17888 KB Output is correct
12 Correct 240 ms 17960 KB Output is correct
13 Correct 257 ms 18128 KB Output is correct
14 Correct 257 ms 18380 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2004 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 93 ms 14248 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 123 ms 17684 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 91 ms 18404 KB Output is correct
9 Correct 95 ms 18236 KB Output is correct
10 Incorrect 109 ms 17888 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 1 ms 1748 KB Output is correct
3 Correct 20 ms 1988 KB Output is correct
4 Correct 21 ms 1984 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 696 KB Output is correct
10 Correct 32 ms 1992 KB Output is correct
11 Correct 28 ms 2000 KB Output is correct
12 Incorrect 28 ms 1900 KB Output isn't correct
13 Halted 0 ms 0 KB -