제출 #157674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157674		nvmdava	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	150 ms	16884 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
 
#define N 200005
#define MOD 1000000007
#define INF 0x3f3f3f3f3f3f3f3f
 
int s[N], e[N], d[N];
vector<int> adj[N];
 
priority_queue<pair<ll, int> > pq;
 
void dij(int v, ll* dis){
	
  memset(dis, 0x3f3f, N);
 
	dis[v] = 0;
	pq.push({0, v});
 
	while(!pq.empty()){
		v = pq.top().ss;
		if(pq.top().ff != -dis[v]){
			pq.pop();
			continue;
		}
		pq.pop();
		for(int& x : adj[v]){
			int u = s[x] ^ e[x] ^ v;
			if(dis[u] > dis[v] + d[x]){
				dis[u] = dis[v] + d[x];
				pq.push({-dis[u], u});
			}
		}
	}
 
}
 
ll dis[3][N];
ll dpmn[2][N];
ll res;
 
void dfs(int v){
	if(dpmn[0][v] != INF) return;
 
	for(int& x : adj[v]){
		int u = s[x] ^ e[x] ^ v;
		if(dis[2][u] == dis[2][v] - d[x]){
			dfs(u);
			dpmn[1][v] = min(dpmn[1][u], dpmn[1][v]);
			dpmn[0][v] = min(dpmn[0][u], dpmn[0][v]);
		}
	}
 
	res = min(res, dpmn[1][v] + dis[0][v]);
	res = min(res, dpmn[0][v] + dis[1][v]);
	dpmn[1][v] = min(dpmn[1][v], dis[1][v]);
	dpmn[0][v] = min(dpmn[0][v], dis[0][v]);
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n, m;
	int ss, tt, uu, vv;
	cin>>n>>m>>ss>>tt>>uu>>vv;
	for(int i = 1; i <= m; i++){
		cin>>s[i]>>e[i]>>d[i];
		adj[s[i]].push_back(i);
		adj[e[i]].push_back(i);
	}
 
	memset(dpmn, 0x3f3f, sizeof dpmn);
 
	dij(uu, dis[0]);
	dij(vv, dis[1]);
	dij(ss, dis[2]);
 
	res = dis[1][uu];
 
	dfs(tt);
 
	cout<<res;
}

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