Submission #833447

#	Time	Username	Problem	Language	Result	Execution time	Memory
833447		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	196 ms	76108 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(v) v.begin(), v.end()
#define fr(m,n,k) for(int m=n;m<=k;m++)
#define frr(m,n,k) for(int m=n;m>=k;m--)
#define yes cout << "YES"
#define no cout << "NO"
#define yesm cout << "Yes"
#define nom cout << "No"
#define inf 1e18
#define ext {cout << -1; return;}
#define zxt {cout << 0; return;}
#define noxt {no;return;}
#define yesxt {yes;return;}
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define rall(a) a.rbegin(),a.rend()
#define lb lower_bound
#define ub upper_bound
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vc vector<char>
#define vb vector<bool>
#define vs vector<string>
#define vpi vector<pi>
#define mii map<int,int>
#define mivi map<int,vi>
#define mci map<char,int>
#define als(i) cout << i.fi << " " << i.se << endl
#define si set<int>
#define msi multiset<int>
#define fi first
#define wq while(q--)
#define se second
#define sz size()
#define el cout<<endl

const int mod = 1e9 + 7;
// const int mod = 998244353;

ll fac(ll n) {ll ans = 1; for (int i = 1; i <= n; ++i) {ans = ans * i;} return ans;}
int binpow(int x, int y) {if (y == 0) return 1; int z = 1; while (y) {	if (y & 1) z = z * x % mod; x = x * x % mod; y >>= 1;} return z;}
int inv(int x) {return binpow(x, mod - 2);}
int bintoint(string s) {reverse(all(s)); int xx = 0; int m = 1; int z = s.sz; fr(j, 0, z) {xx += (s[j] == '1' ? m : 0); m <<= 1;} return xx;}
string inttobin(int x) {if (x == 0) return "0"; string s; while (x) {s += (x & 1) + '0'; x >>= 1;} reverse(all(s)); return s;}
int add(int x, int y) {int zz = ((x + y) % mod + mod) % mod; return zz;}
string ads(string s, string p) {if (s.sz > p.sz)swap(s, p); int n = s.sz, m = p.sz; reverse(all(s)); reverse(all(p)); int tm = 0; string st; fr(i, 0, n) {int k = s[i] - '0' + p[i] - '0' + tm; st += ('0' + k % 10); tm = k / 10;} fr(i, n, m) {    int k = p[i] - '0' + tm; st += ('0' + k % 10); tm = k / 10;} if (tm) st += (tm + '0'); reverse(all(st)); return st;}

const int N = 5e5 + 5;
int n, m, k, l, r, w, a, b, c, d, e, x, y, z;
int mi = inf, ma = 0, sum = 0, ans = 0, num = 0, cnt = 0;
vpi adj[N];
vi back[N];
int dis[N]; vi tanda;

void solve() {
	int s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	fr(i, 0, m - 1) {
		cin >> a >> b >> w;
		adj[a].pb({b, w});
		adj[b].pb({a, w});
	}
	priority_queue<pi, vpi, greater<pi>>pq;
	fr(i, 1, n) dis[i] = 1e10;
	pq.push({0, s}); dis[s] = 0;
	// if (s == u) {
	// 	while (!pq.empty()) {
	// 		auto [w, x] = pq.top(); pq.pop();
	// 		for (auto z : adj[x]) {
	// 			auto [y, jr] = z;
	// 			if (dis[y] > jr + dis[x]) {
	// 				back[y].clear();
	// 				back[y].pb(x);
	// 				dis[y] = jr + dis[x];
	// 				pq.push({dis[y], y});
	// 			}
	// 			else if (dis[y] == jr + dis[x]) {
	// 				back[y].pb(x);
	// 			}
	// 		}
	// 	}
	// 	queue<int>lis; lis.push(t);
	// 	while (lis.sz) {
	// 		auto x = lis.front(); lis.pop();
	// 		tanda.pb(x);
	// 		for (auto z : back[x]) {
	// 			lis.push(z);
	// 		}
	// 	}

	// 	fr(i, 1, n) dis[i] = 1e10;
	// 	pq.push({0, v}); dis[v] = 0;
	// 	while (!pq.empty()) {
	// 		auto [w, x] = pq.top(); pq.pop();
	// 		for (auto z : adj[x]) {
	// 			auto [y, d] = z;
	// 			if (dis[y] > d + w) {
	// 				dis[y] = d + w;
	// 				pq.push({dis[y], y});
	// 			}
	// 		}
	// 	}

	// 	mi = inf;
	// 	for (auto z : tanda) {
	// 		mi = min(mi, dis[z]);
	// 	}
	// 	cout << mi;
	// }
	// else {
	while (!pq.empty()) {
		auto [w, x] = pq.top(); pq.pop();
		for (auto z : adj[x]) {
			auto [y, jr] = z;
			if (dis[y] > jr + dis[x]) {
				back[y].pb(x);
				dis[y] = jr + dis[x];
				pq.push({dis[y], y});
			}
		}
	}
	k = t;
	while (true) {
		if (k == s) break;
		l = back[k][0];
		pi p = {k, 0}; auto z = lb(all(adj[l]), p) - adj[l].begin();
		adj[l][z].se = 0;
		p = {l, 0}; z = lb(all(adj[k]), p) - adj[k].begin();
		adj[k][z].se = 0;
		k = l;
	}

	fr(i, 1, n) dis[i] = 1e10;
	pq.push({0, v}); dis[v] = 0;
	while (!pq.empty()) {
		auto [w, x] = pq.top(); pq.pop();
		for (auto z : adj[x]) {
			auto [y, jr] = z;
			if (dis[y] > jr + dis[x]) {
				dis[y] = jr + dis[x];
				pq.push({dis[y], y});
			}
		}
	}
	cout << dis[u];
	// }
}
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
	int T = 1;
	// cin >> T;
	while (T--) {
		cout << fixed << setprecision(12); solve();
		cout << endl;
	} return 0;
}

// TULIS !!! / liat sebaliknya / semuanya / sebagian
// out of bounds / overflor / array bounds
// answer minus, edge test case / special tc
// TLE/MLE
// check other approach / solusi jangan terlalu ribet

/*
brute force, greedy,pref sum / xor / factor / prime,2pointer,gcd/lcm,even/odd
,min/max,binsearch, bfs/dfs,iterate,multiple/divisor

DSU, bipartite graph,bitmasking, sliding window,konstanta
divconquer,bitmasking, konstanta,djikstra,stack,queue,scanline
coordinate compression,sparse table,prefix difference,segtree,dp,
*/
// tools :
//__lg(x),__builtinpopcount,nextpermutation(), is_sorted / alpha / digit,

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