Submission #157677

#	Time	Username	Problem	Language	Result	Execution time	Memory
157677		nvmdava	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	366 ms	23784 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
 
#define N 200005
#define INF 0x3f3f3f3f3f3f3f3f

int e[N], d[N], n, m, s, t, u, v;
vector<int> adj[N];

priority_queue<pair<ll, int> > p;

void dij(int v, ll* dis){
	
	memset(dis, 0x3f3f, N << 3);

	dis[v] = 0;
	p.push({0, v});

	while(!p.empty()){
		v = p.top().ss;
		if(p.top().ff != -dis[v]){
			p.pop();
			continue;
		}
		p.pop();
		for(int& x : adj[v]){
			int u = e[x] ^ v;
			if(dis[u] > dis[v] + d[x]){
				dis[u] = dis[v] + d[x];
				p.push({-dis[u], u});
			}
		}
	}

}

ll dis[3][N], dp[2][N], res;

void dfs(int v){
	if(dp[0][v] != INF) return;
	
	dp[1][v] = dis[1][v];
	dp[0][v] = dis[0][v];
	
	for(int& x : adj[v]){
		int u = e[x] ^ v;
		if(dis[2][u] == dis[2][v] - d[x]){
			dfs(u);
			dp[1][v] = min(dp[1][u], dp[1][v]);
			dp[0][v] = min(dp[0][u], dp[0][v]);
		}
	}

	res = min(res, min(dp[1][v] + dis[0][v], dp[0][v] + dis[1][v]));
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n>>m>>s>>t>>u>>v;

	for(int a, b, i = 1; i <= m; i++){
		cin>>a>>b>>d[i];
		e[i] = a ^ b;
		adj[a].push_back(i);
		adj[b].push_back(i);
	}

	memset(dp, 0x3f3f, sizeof dp);

	dij(u, dis[0]);
	dij(v, dis[1]);
	dij(s, dis[2]);

	res = dis[1][u];

	dfs(t);

	cout<<res;
}

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