Submission #769374

#	Time	Username	Problem	Language	Result	Execution time	Memory
769374		NintsiChkhaidze	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	969 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 1e5 + 5,inf = 1e18;

vector <pii> g[N];
int id[N],dis[7][N];
int dp[N],n,s,t,u,v;

void go(int x,int idx){
	id[x] = idx;
	
	for (int i = 1; i <= n; i++)
		dis[idx][i] = inf;
	
	priority_queue <pii> pq;
	dis[idx][x] = 0;
	pq.push({0,x});
	while (pq.size()){
		int d = -pq.top().f,x = pq.top().s;
		pq.pop();
		if (dis[idx][x] != d) continue;
		
		for (auto [to,w]: g[x]){
			if (dis[idx][to] > dis[idx][x] + w) {
				dis[idx][to] = d + w;
				pq.push({-d-w,to});
			}
		}
	}
}

void G(int x){
	int idx = id[x];
	for (int i= 1; i <= n; i++)
		dis[idx][i] = inf,dp[i] = inf;
	
	priority_queue <pii> pq;
	dis[idx][x] = 0;
	dp[x] = dis[id[v]][x];
	pq.push({0,x});
	
	while (pq.size()){
		int d = -pq.top().f,x = pq.top().s;
		pq.pop();
		if (dis[idx][x] != d) continue;
		
		for (auto [to,w]: g[x]){
			if (dis[idx][to] >= d + w){
				dis[idx][to] = d + w;
				dp[to] = min({dp[x],dp[to], dis[id[v]][to]});
				pq.push({-d-w,to});
			}
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int m;
	cin>>n>>m;
	cin>>s>>t>>u>>v;
	
	for (int i= 1; i <= m; i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}
	
	go(s,1);
	go(t,2);
	go(u,3);
	go(v,4);
	
	int ans = dis[id[u]][v];
	ll lenst = dis[id[s]][t];
	
	G(t);
	for (int i= 1; i <= n; i++){
		if (dis[id[s]][i] + dis[id[t]][i] != lenst) continue;
		ans = min(ans, dp[i] + dis[id[u]][i]);
	}
	
	G(s);
	for (int i = 1; i <= n; i++){
		if (dis[id[s]][i] + dis[id[t]][i] != lenst) continue;
		ans = min(ans,dp[i] + dis[id[u]][i]);
	}
	cout<<ans;
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
*/

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