Submission #234915

#	Time	Username	Problem	Language	Result	Execution time	Memory
234915		amoo_safar	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	602 ms	35716 KiB

commuter_pass

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll dis[2][N];
vector<pll> G[N];

set<pll> st;

void Dij(int sc, int idx){
	memset(dis[idx], 31, sizeof dis[idx]);
	dis[idx][sc] = 0;
	st.insert({0, sc});
	int fr;
	while(!st.empty()){
		fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto ed : G[fr]){
			if(dis[idx][ed.F] > dis[idx][fr] + ed.S){
				st.erase({dis[idx][ed.F], ed.F});
				dis[idx][ed.F] = dis[idx][fr] + ed.S;
				st.insert({dis[idx][ed.F], ed.F});
			}
		}
	}
}

ll dp[N][4], d[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m;
	cin >> n >> m;
	ll s, t, l1, l2;
	cin >> s >> t >> l1 >> l2;
	ll u, v, w;
	for(int i = 0; i < m; i++){
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	Dij(l1, 0);
	Dij(l2, 1);
	memset(dp, 31, sizeof dp);
	memset(d, 31, sizeof d);
	for(int i = 0; i < 4; i++) dp[s][i] = (i & 1 ? dis[0][s] : 0) + (i & 2 ? dis[1][s] : 0);
	d[s] = 0;
	st.insert({d[s], s});
	int fr, adj;
	while(!st.empty()){
		fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto e : G[fr]){
			adj = e.F;
			if(d[adj] > d[fr] + e.S){
				st.erase({d[adj], adj});
				d[adj] = d[fr] + e.S;
				st.insert({d[adj], adj});
				memset(dp[adj], 31, sizeof dp[adj]);
			}
			if(d[adj] == d[fr] + e.S){
				for(int mk1 = 0; mk1 < 4; mk1 ++){
					for(int mk2 = 0; mk2 < 4; mk2 ++){
						if(mk1 & mk2) continue;
						dp[adj][mk1 | mk2] = min(dp[adj][mk1 | mk2], dp[fr][mk1] + (mk2 & 1 ? dis[0][adj] : 0) + (mk2 & 2 ? dis[1][adj] : 0));
					}
				}
			}
		}
	}

	cout << min(dis[0][l2], dp[t][3]) << '\n';
	return 0;
}

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