Submission #1180435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180435		miniob	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	172 ms	19436 KiB

commuter_pass

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

vector<pair<long long, long long>> graph[100007];
long long odl[100007][4];// 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});
			}
		}
	}
}

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});
	}
	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] && i < x.first)
			{
				graph[i].push_back({x.first, 0});
			}
		}
	}
	djikstra(u, 2);
	djikstra(v, 3);
	cout << min(odl[v][2], odl[u][3]) << endl;
	return 0;
}

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