Submission #989976

#	Time	Username	Problem	Language	Result	Execution time	Memory
989976		Muhammet	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	243 ms	41996 KiB

commuter_pass

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

#define N 300005
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

ll T, n, m, s, t, u1, u2, dis[N], a[N], b[N], c[N];

vector <pair<int,int>> v[N];

map <pair<int,int>, bool> vis;

void dfs(int x){
	for(auto i : v[x]){
		if(dis[x] == dis[i.ff] + i.ss){
			vis[{x,i.ff}] = 1;
			vis[{i.ff,x}] = 1;
			dfs(i.ff);
			return;
		}
	}
}

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

	cin >> n >> m >> s >> t >> u1 >> u2;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
		v[a[i]].push_back({b[i],c[i]});
		v[b[i]].push_back({a[i],c[i]});
	}

	for(int i = 1; i <= n; i++) dis[i] = 1e15;

	priority_queue <pair<ll,ll>> q;
	q.push({0,s});
	dis[s] = 0;

	while(!q.empty()){
		int x = q.top().ss;
		if(dis[x] != -q.top().ff){
			q.pop();
			continue;
		}
		q.pop();

		for(auto i : v[x]){
			if(dis[i.ff] > dis[x] + i.ss){
				dis[i.ff] = dis[x] + i.ss;
				q.push({-dis[i.ff], i.ff});
			}
		}
	}

	dfs(t);

	for(int i = 1; i <= n; i++) v[i].clear();
	for(int i = 1; i <= m; i++){
		if(vis[{a[i],b[i]}] == 0){
			v[a[i]].push_back({b[i],c[i]});
			v[b[i]].push_back({a[i],c[i]});
		}
		else {
			v[a[i]].push_back({b[i],0});
			v[b[i]].push_back({a[i],0});
		}
	}

	for(int i = 1; i <= n; i++) dis[i] = 1e15;

	q.push({0,u1});
	dis[u1] = 0;

	while(!q.empty()){
		int x = q.top().ss;
		if(dis[x] != -q.top().ff){
			q.pop();
			continue;
		}
		q.pop();

		for(auto i : v[x]){
			if(dis[i.ff] > dis[x] + i.ss){
				dis[i.ff] = dis[x] + i.ss;
				q.push({-dis[i.ff], i.ff});
			}
		}
	}

	cout << dis[u2];

	return 0;
}

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