Submission #1198616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198616		mehralii	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	103 ms	27212 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define MAXN 100000
#define LOG (int)log2(MAXN)+1

const int INF = 1e18;
const int MOD = 998244353;
const double EPS = 1e-8;

//15 p.

int N, M, S, T, U, V;
vector<vector<pair<int, int>>> g;
int d1[MAXN], d2[MAXN], dist[MAXN];
vector<tuple<int, int, int>> edges;
map<pair<int, int>, bool> used;

void init(){
	g.resize(N+1);
	fill(d1, d1+MAXN, INF);
	fill(d2, d2+MAXN, INF);
	fill(dist, dist+MAXN, INF);
}

void dijkstra1(){
	set<pair<int, int>> q;
	q.ins({d1[S]=0, S});
	int u, w;
	while(!q.empty()){
		tie(w, u) = *q.begin();
		q.erase(q.begin());
		for(auto&[to, W]:g[u]){
			if(w+W<d1[to]){
				d1[to] = w+W;
				q.ins({d1[to], to});
			}
		}
	}
	int dist = d1[T];
	q.ins({d2[T] = 0, T});
	while(!q.empty()){
		tie(w, u) = *q.begin();
		q.erase(q.begin());
		for(auto&[to, W]:g[u]){
			if(w+W<d2[to]){
				d2[to] = w+W;
				q.ins({d2[to], to});
			}
		}
	}
	int v;
	for(int i = 0; i < edges.size(); i++){
		tie(u, v, w) = edges[i];
		if(d1[u]+d2[v]+w==dist){
			used[{u, v}] = 1;
			used[{v, u}] = 1;
		}
	}
}

void dijkstra2(){
	set<pair<int, int>> q;
	q.ins({dist[U] = 0, U});
	int u, w;
	while(!q.empty()){
		tie(w, u) = *q.begin();
		q.erase(q.begin());
		for(auto&[to, W]:g[u]){
			int tW = (used[{u, to}]?0: W);
			if(w+tW<dist[to]){
				dist[to] = w+tW;
				q.ins({dist[to], to});
			}
		}
	}
}

void solve() {
	cin >> N >> M >> S >>T >> U >> V;
	init();
	for(int i = 0; i < M; i++){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		edges.pb({u, v, w});
		edges.pb({v, u, w});
	}
	dijkstra1();
	dijkstra2();
	cout << dist[V] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) solve();
    return 0;
}

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