Submission #769416

#	Time	Username	Problem	Language	Result	Execution time	Memory
769416		NintsiChkhaidze	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	289 ms	25596 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 <ll,int>
using namespace std;

const int N = 2e5 + 5;
const ll inf = 1e18;

vector <pii> g[N];
int id[N];
bool vis[N];
ll dis[7][N],dp[N],dd[N],lenst;
int 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({0LL,x});
	while (pq.size()){
		ll d = -pq.top().f; int 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++)
		dd[i] = inf,dp[i] = inf,vis[i]=0;
	
	priority_queue <pii> pq;
	dd[x] = 0;
	dp[x] = dis[id[v]][x];
	pq.push({0LL,x});
	
	while (pq.size()){
		ll d = -pq.top().f; int x = pq.top().s;
		pq.pop();
		if (vis[x]) continue;
		vis[x]=1;
		
		for (auto [to,w]: g[x]){
			if (dis[id[s]][to] + dis[id[t]][to] != lenst) continue;
			if (dd[to] >= d + w){
				dd[to] = d + w;
				dp[to] = min({dp[x],dp[to], dis[id[v]][to]});
				if (!vis[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);
	
	ll ans = dis[id[u]][v];
	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;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void G(int)':
commuter_pass.cpp:44:6: warning: unused variable 'idx' [-Wunused-variable]
   44 |  int idx = id[x];
      |      ^~~

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