Submission #847103

#	Time	Username	Problem	Language	Result	Execution time	Memory
847103		ZeroScar	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	514 ms	43804 KiB

commuter_pass

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

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//using ordered_set = tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;
//using ordered_multiset = tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>;
//#define fbo find_by_order // use pointer, returns kth element (0-based)
//#define ook order_of_key // returns x ada di index berapa (0-based)

#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define lll __int128
#define tp top()
#define fr front()

#define sz size()
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define mem(a,  b) memset(a,  (b),  sizeof(a))
#define clr(a) memset(a,  0,  sizeof(a))
#define sqr(x) ( (x) * (x) )
#define all(v) v.begin(),  v.end()
#define rall(v) v.rbegin(),  v.rend()

template<typename T>
using ve = vector<T>;
using pii = pair<int,int>;
using ppi = pair<pii,int>;
using pip = pair<int,pii>;
using ppp = pair<pii,pii>;


void optIO(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int N = 100020;
const ll INF = 1e18;

using pll = pair<ll,ll>;
using pli = pair<pll,int>;
vector<pli> adj[N];
ll dist[N];


void dijkstra(int s, int t) {
	
	for(int i = 0; i < N; i++) dist[i] = INF;
	
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	pq.push({0,s});
	while(pq.sz) {
		ll d = pq.tp.fi;
		int x = pq.tp.se;
		pq.pop();
		
		if (dist[x] <= d) continue;
		dist[x] = d;
		
		for(auto to : adj[x]) pq.push({d + to.fi.se, to.fi.fi});
	}
	
	set<pll> ms;
	ms.insert({dist[t], t});
	
	while(ms.sz) {
		auto it = *(ms.rbegin());
		ms.erase(it);
		
		int cur = it.se;
		for(auto &to : adj[cur]) if (dist[to.fi.fi] + to.fi.se == dist[cur]) {
			to.se = 1;
			ms.insert({dist[to.fi.fi], to.fi.fi});
		}
	}
}

ll dij(int s, int t) {
	bool vis[N][3] = {0};
	
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	pq.push({{0,s},0});
	while(pq.sz) {
		ll d = pq.tp.fi.fi;
		ll x = pq.tp.fi.se;
		int st = pq.tp.se;
		pq.pop();
		
		if (vis[x][st]) continue;
		vis[x][st] = 1;
		
		if (x == t) return d;
		
		for(auto &to : adj[x]) {
			
			if (st == 2) pq.push({{d + to.fi.se,to.fi.fi},2});
			else if (st == 1) {
				if (to.se == 1 && dist[x] == dist[to.fi.fi] + to.fi.se) pq.push({{d,to.fi.fi},1});
				else pq.push({{d + to.fi.se,to.fi.fi},2});
			} else {
				if (to.se == 1 && dist[x] == dist[to.fi.fi] + to.fi.se) pq.push({{d,to.fi.fi},1});
				pq.push({{d + to.fi.se,to.fi.fi},0});
			}
		}
	}
	return 0;
}

void solve(){
	int n,m; cin>>n>>m; 
	int s,t; cin>>s>>t;
	int u,v; cin>>u>>v;
	while(m--){
		int uu,vv,ww; cin>>uu>>vv>>ww;
		adj[uu].pb({{vv,ww}, 0});
		adj[vv].pb({{uu,ww}, 0});
	}
	
	dijkstra(s,t);
	
	cout<<min(dij(u,v), dij(v,u))<<"\n";
}

int main() {
	optIO();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

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