Submission #1194207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194207		PlayVoltz	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	369 ms	26128 KiB

commuter_pass

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
vector<int> du, dv;
vector<vector<pii> > graph;

vector<int> dijk(int s){
	vector<int> dj(n+1, LLONG_MAX/2);
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	dj[s]=0;
	pq.push(mp(0, s));
	while (pq.size()){
		int d=pq.top().fi, node=pq.top().se;
		pq.pop();
		if (d!=dj[node])continue;
		for (auto num:graph[node])if (dj[node]+num.se<dj[num.fi]){
			dj[num.fi]=dj[node]+num.se;
			pq.push(mp(dj[num.fi], num.fi));
		}
	}
	return dj;
}

int dijk2(int s, int t){
	vector<int> dj(n+1, LLONG_MAX/2), u(n+1, LLONG_MAX/2), v(n+1, LLONG_MAX/2);
	vector<bool> visited(n+1, 0);
	priority_queue<pair<int, pii>, vector<pair<int, pii> >, greater<pair<int, pii> > > pq;
	pq.push(mp(0, mp(s, 0)));
	while (pq.size()){
		int d=pq.top().fi, node=pq.top().se.fi, par=pq.top().se.se;
		pq.pop();
		if (!visited[node]){
			visited[node]=1;
			dj[node]=d;
			u[node]=min(u[par], du[node]);
			v[node]=min(v[par], dv[node]);
			for (auto num:graph[node])pq.push(mp(d+num.se, mp(num.fi, node)));
		}
		else if (d==dj[node]&&min(u[par], du[node])+min(v[par], dv[node])<u[node]+v[node]){
			u[node]=min(u[par], du[node]);
			v[node]=min(v[par], dv[node]);
		}
	}
	return u[t]+v[t];
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int m, s, t, u, v, a, b, c;
	cin>>n>>m>>s>>t>>u>>v;
	graph.resize(n+1);
	while (m--){
		cin>>a>>b>>c;
		graph[a].pb(mp(b, c));
		graph[b].pb(mp(a, c));
	}
	du=dijk(u), dv=dijk(v);
	cout<<min(du[v], dijk2(s, t));
}

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