Submission #944110

#	Time	Username	Problem	Language	Result	Execution time	Memory
944110		Amaarsaa	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	296 ms	26284 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
vector < pll > adj[100005];
ll cnt = 0;
ll D[5][100005], Used[100005] = {0};

void Djik(ll s) {
	ll x, X;
	priority_queue < pll, vector < pll > , greater < pll > > pq;
	D[cnt][s] = 0;
	pq.push({0, s});
	while(!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		for ( pll P : adj[x]) {
			X = P.first;
			if ( D[cnt][X] > D[cnt][x] + P.second) {
				D[cnt][X] = D[cnt][x] + P.second;
				pq.push({D[cnt][X], X});
			}
		}
		
	}
	
}
ll D1[100005], D2[100005], d1[100005], d2[100005];
int main() {
	ll n, m , s, t, u, ans, v, i, x, y, c;
	
	cin >> n >> m >> s >> t >> u >> v;
	
	for (i = 1; i <= m; i ++) {
		cin >> x >> y >> c;
		adj[x].push_back({y, c});
		adj[y].push_back({x, c});
	}
	memset(D, 127, sizeof D);
	cnt ++;
	Djik(u);
	cnt ++;
	Djik(v);
	cnt ++;
	ll X;
	priority_queue < pll, vector < pll > , greater < pll > > pq;
	D[cnt][s] = 0;
	ans = D[1][v];
	for (i = 1; i <= n; i ++) {
		d1[i] = 1e18;
		d2[i] = 1e18;
		D1[i] = D[1][i];
		D2[i] = D[2][i];
	}
	d1[s] = D1[s];
	d2[s] = D2[s];
	pq.push({0, s});
	while(!pq.empty()) {
		x = pq.top().second;
		pq.pop();
		if ( Used[x] == 1) continue;
		Used[x] = 1;
		
		for ( pll P : adj[x]) {
			X = P.first;
			if ( D[cnt][X] > D[cnt][x] + P.second) {
				D[cnt][X] = D[cnt][x] + P.second;
				d1[X] = min(d1[x], D1[X]);
				d2[X] = min(d2[x], D2[X]);
				pq.push({D[cnt][X], X});
			}
			else {
				if ( d1[x] + d2[x] < d1[X] + d2[X]) {
					d1[X] = d1[x];
					d2[X] = d2[x];
				}
					
			}
		}
	}
	cout << d1[t] + d2[t] << endl;
	
	
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:31:21: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   31 |  ll n, m , s, t, u, ans, v, i, x, y, c;
      |                     ^~~

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