Submission #521576

#	Time	Username	Problem	Language	Result	Execution time	Memory
521576		AdamGS	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	422 ms	27320 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll INF=1e18+7;
vector<pair<int,ll>>V[LIM];
ll wart[LIM][2], odl[LIM][2], mi[LIM][2], n, m;
void dijkstra1(int x, int k) {
	rep(i, n) wart[i][k]=INF;
	priority_queue<pair<ll,int>>q;
	q.push({0, x});
	while(!q.empty()) {
		ll o=-q.top().st, p=q.top().nd; q.pop();
		if(wart[p][k]<=o) continue;
		wart[p][k]=o;
		for(auto i : V[p]) if(o+i.nd<wart[i.st][k]) {
			q.push({-o-i.nd, i.st});
		}
	}
}
void dijkstra2(int x, int k) {
	rep(i, n) odl[i][k]=mi[i][k]=INF;
	priority_queue<pair<pair<ll,ll>,int>>q;
	q.push({{0, -wart[x][0]}, x});
	while(!q.empty()) {
		ll a=-q.top().st.st, b=-q.top().st.nd, p=q.top().nd; q.pop();
		if(odl[p][k]<a) continue;
		if(odl[p][k]==a && mi[p][k]<=b) continue;
		odl[p][k]=a;
		mi[p][k]=b;
		for(auto i : V[p]) {
			if(a+i.nd<odl[i.st][k] || a+i.nd==odl[i.st][k] && min(b, wart[i.st][0])<mi[i.st][0]) {
				q.push({{-a-i.nd, -min(b, wart[i.st][0])}, i.st});
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	--s; --t; --u; --v;
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c; --a; --b;
		V[a].pb({b, c});
		V[b].pb({a, c});
	}
	dijkstra1(u, 0);
	dijkstra1(v, 1);
	dijkstra2(s, 0);
	dijkstra2(t, 1);
	ll ans=wart[v][0];
	rep(i, n) if(odl[i][0]+odl[i][1]==odl[t][0]) {
		ans=min(ans, wart[i][1]+min(mi[i][0], mi[i][1]));
	}
	cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:38:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |    if(a+i.nd<odl[i.st][k] || a+i.nd==odl[i.st][k] && min(b, wart[i.st][0])<mi[i.st][0]) {
      |                              ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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