Submission #1180447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180447		miniob	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	533 ms	48824 KiB

commuter_pass

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

vector<pair<long long, long long>> graph[100007];
vector<pair<long long, long long>> graph2[200007];
long long odl[100007][2];// s t u v
long long odl2[200007][2];// s t u v
long long n;

void djikstra(long long s, long long kt)
{
	for(long long i = 1; i <= n; i++)
	{
		odl[i][kt] = LLONG_MAX;
	}
	odl[s][kt] = 0;
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
	pq.push({0, s});
	while(!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();
		for(auto x : graph[cur.second])
		{
			if(odl[x.first][kt] > odl[cur.second][kt] + x.second)
			{
				odl[x.first][kt] = odl[cur.second][kt] + x.second;
				pq.push({odl[x.first][kt], x.first});
			}
		}
	}
}

void djikstra2(long long s, long long kt)
{
	for(long long i = 1; i <= 100000 + n; i++)
	{
		odl2[i][kt] = LLONG_MAX;
	}
	odl2[s][kt] = 0;
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
	pq.push({0, s});
	while(!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();
		for(auto x : graph2[cur.second])
		{
			if(odl2[x.first][kt] > odl2[cur.second][kt] + x.second)
			{
				odl2[x.first][kt] = odl2[cur.second][kt] + x.second;
				pq.push({odl2[x.first][kt], x.first});
			}
		}
	}
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for(long long i = 0; i < m; i++)
	{
		long long a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
		graph2[a].push_back({b, c});
		graph2[b].push_back({a, c});
		graph2[a + 100000].push_back({b + 100000, c});
		graph2[b + 100000].push_back({a + 100000, c});
	}
	djikstra(s, 0);
	djikstra(t, 1);
	for(long long i = 1; i <= n; i++)
	{
		for(auto x : graph[i])
		{
			if(odl[i][0] + odl[x.first][1] + x.second == odl[t][0] && odl[i][0] < odl[x.first][0])
			{
				graph2[i].push_back({x.first + 100000, 0});
			}
		}
	}
	djikstra2(u, 0);
	djikstra2(v, 1);
	cout << min(min(odl2[v][0], odl2[u][1]), min(odl2[v + 100000][0], odl2[u + 100000][1]))  << endl;
	return 0;
}

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