제출 #1309941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309941		zowi	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	187 ms	19968 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> graf[100005];
vector<int> dag[100005];
bool odw[100005];
long long odl[100005][3];
bool czy[100005];
long long dp[100005];
long long dp1[100005];
int topo[100005];

void dij(long long x,long long y,long long n)
{
	for(long long i = 1;i <= n;++i)
	{
		odl[i][y] = 1e18;
	}
	priority_queue<pair<long long,long long>> kol;
	odl[x][y] = 0;
	kol.push({0,x});
	long long a,b;
	while(kol.size())
	{
		a = -kol.top().first;
		b = kol.top().second;
		kol.pop();
		if(odl[b][y] == a)
		{
			for(pair<long long,long long> i : graf[b])
			{
				if(odl[i.first][y] > a+i.second)
				{
					odl[i.first][y] = a+i.second;
					kol.push({-(a+i.second),i.first});
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n,m,u,t,s,v,a,b,c;
	cin >> n >> m >> s >> t >> u >> v;
	for(long long i = 0;i < m;++i)
	{
		cin >> a >> b >> c;
		graf[a].push_back({b,c});
		graf[b].push_back({a,c});
	}
	dij(s,0,n);
	queue<long long> kol;
	kol.push(t);
	czy[t] = 1;
	//set<pair<int,int>> cz;
	while(kol.size())
	{
		a = kol.front();
		kol.pop();
		for(pair<long long,long long> i : graf[a])
		{
			if(odl[a][0]-i.second == odl[i.first][0])
			{
				dag[i.first].push_back(a);
                //topo[a]++;
                if(!czy[i.first])
                {
                    czy[i.first]=true;
                    kol.push(i.first);
                }
			}
		}
	}
	for(long long i = 1;i <= n;++i)
	{
		dp[i] = 1e18;
		dp1[i] = 1e18;
		for(int j : dag[i])
		{
			topo[j]++;
			//cout << i << ' ' << j.first << endl;
		}
	}
	dij(u,1,n);
	dij(v,2,n);
	kol.push(s);
	long long wyn = 1e18;
	while(kol.size())
	{
		a = kol.front();
		kol.pop();
		dp[a] = min(dp[a],odl[a][1]);
		dp1[a] = min(dp1[a],odl[a][2]);
		wyn = min(wyn,dp[a]+odl[a][2]);
		wyn = min(wyn,dp1[a]+odl[a][1]);
		for(int i : dag[a])
		{
			topo[i]--;
			dp[i] = min(dp[i],dp[a]);
			dp1[i] = min(dp1[i],dp1[a]);
			if(topo[i] == 0)
			{
				kol.push(i);
			}
		}
	}
	/*for(long long i = 1;i <= n;++i)
	{
		cout << odl[i][1] << ' ';
	}
	cout << endl;
	for(long long i = 1;i <= n;++i)
	{
		cout << odl[i][2] << ' ';
	}cout << endl;
	for(long long i = 1;i <= n;++i)
	{
		cout << dp[i] << ' ';
	}cout << endl;*/
	cout << min(wyn,odl[u][2]);
	/*for(long long i = 1;i <= n;++i)
	{
		if(czy[i] == 1)
		{
			for(pair<long long,long long> j : graf[i])
			{
				if(czy[j.first] == 1)
				{
					dag[i].push_back(j);
					dag[j.first].push_back({i,j.second});
				}
			}
		}
	}*/
	
	
	
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45