Submission #1309932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309932		zowi	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2101 ms	144508 KiB

commuter_pass

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

vector<pair<long long,long long>> graf[100005];
vector<pair<long long,long long>> dag[100005];
long long odw[100005];
long long odl[100005][5];
long long czy[100005];
long long dp[100005];
long long dp1[100005];
long long 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);
	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<long long,long long>> 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])
			{
				if(cz.find({i.first,a}) == cz.end())
				{
					dag[i.first].push_back({a,i.second});
					cz.insert({i.first,a});
				}
				czy[i.first] = 1;
				kol.push(i.first);
			}
		}
	}
	for(long long i = 1;i <= n;++i)
	{
		dp[i] = 1e18;
		dp1[i] = 1e18;
		for(pair<long long,long long> j : dag[i])
		{
			topo[j.first]++;
			//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(pair<long long,long long> i : dag[a])
		{
			topo[i.first]--;
			dp[i.first] = min(dp[i.first],dp[a]);
			dp1[i.first] = min(dp1[i.first],dp1[a]);
			if(topo[i.first] == 0)
			{
				kol.push(i.first);
			}
		}
	}
	/*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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45