Submission #1141617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141617		KK_1729	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	392 ms	27972 KiB

commuter_pass

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

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back 
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}

vector<vector<pair<int, int>>> graph;
vector<int> distu;
vector<int> distv;
vector<int> dp1;

vector<int> dp2;

void dijkstra(int s, int n, vector<int> &arr){
	arr[s] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({0, s});
	vector<int> visited(n+1);
	while (!pq.empty()){
		int c, node;
		tie(c, node) = pq.top();
		pq.pop();

		if (!visited[node]){
			arr[node] = -c;
			visited[node] = 1;
			for (auto x: graph[node]) pq.push({c-x.second, x.first});
		}
		
	}
}
int ans = 1e17;
void dijkstra2(int s, int e, int n){
	vector<int> visited(n+1);
	vector<int> ds(n+1, 1e17);
	dp1.resize(n+1, 1e17);
	dp2.resize(n+1, 1e17);
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({0, {s, 0}});
	
	while (!pq.empty()){
		int c, node, par;
		pair<int, int> p;
		tie(c, p) = pq.top();
		pq.pop();
		tie(node, par) = p;

		if (!visited[node]){
			visited[node] = 1;
			ds[node] = -c;
			dp1[node] = min(distu[node], dp1[par]);
			dp2[node] = min(distv[node], dp2[par]);
			for (auto x: graph[node]) pq.push({c-x.second, {x.first, node}});
		}else if (-c == ds[node]){
			if (min(distu[node], dp1[par])+min(distv[node], dp2[par]) <=
				dp1[node]+dp2[node]){
					dp1[node] = min(distu[node], dp1[par]);
					dp2[node] = min(distv[node], dp2[par]);
				}
		}
	}
	ans = min(ans, dp1[e]+dp2[e]);

}
void solve(){
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	graph.resize(n+1);
	distu.resize(n+1, 1e17);
	distv.resize(n+1, 1e17);
	dp1.resize(n+1, 1e17);
	dp2.resize(n+1, 1e17);
	FOR(i,0,m){
		int a, b, c; cin >> a >> b >> c;
		graph[a].pb({b, c});
		graph[b].pb({a, c});
	}

	dijkstra(u, n, distu);
	dijkstra(v, n, distv);

	ans = distu[v];

	dijkstra2(s, t, n);
	dp1.clear();
	dp2.clear();
	dijkstra2(t, s, n);
	cout << ans << endl;
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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