Submission #1129418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129418		euthymia2606	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	239 ms	19984 KiB

commuter_pass

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

template<typename T>
bool minimize(T& a, const T& b) {
	if (b < a) {a = b; return true;}
	return false;
}

const int N = 1e5 + 5;  

int n, m; 
int s, t, a, b;  
vector<ii> adj[N]; 

struct Node {
	int u; ll d; 
	bool operator<(const Node& other) const {
		return d > other.d; 
	}
};

ll dist_s[N]; 
ll dist_t[N]; 
ll dist_a[N]; 
ll dist_b[N]; 

void dijkstra(int s, ll dist[]) {
	for (int u = 1; u <= n; u++) dist[u] = LINF;  

	priority_queue<Node> pq; 
	dist[s] = 0;  
	pq.push({s, dist[s]});  

	while (!pq.empty()) {
		Node front = pq.top(); pq.pop(); 
		int u = front.u; ll d = front.d;  

		if (d > dist[u]) continue; 

		for (ii v : adj[u]) {
			if (minimize(dist[v.first], dist[u] + v.second)) {
				pq.push({v.first, dist[v.first]}); 
			}
		}
	}
}

vector<int> g[N]; 

ll memo[N];  

ll dp_a(int u) {
	ll& ans = memo[u];  
	if (ans != -1) return ans; 
	ans = dist_a[u];  
	for (int v : g[u]) {
		minimize(ans, dp_a(v)); 
	}
	return ans; 
}

ll dp_b(int u) {
	ll& ans = memo[u];  
	if (ans != -1) return ans; 
	ans = dist_b[u]; 
	for (int v : g[u]) {
		minimize(ans, dp_b(v)); 
	}
	return ans; 
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> n >> m; 
	cin >> s >> t; 
	cin >> a >> b;   

	for (int i = 0; i < m; i++) {
		int u, v, w; 
		cin >> u >> v >> w; 
		adj[u].push_back({v, w}); 
		adj[v].push_back({u, w}); 
	}

	dijkstra(s, dist_s); 
	dijkstra(t, dist_t); 
	
	for (int u = 1; u <= n; u++) {
		for (ii v : adj[u]) {
			if (dist_s[u] + v.second + dist_t[v.first] == dist_s[t]) {
				g[u].push_back(v.first); 
			}
		}
	}

	dijkstra(a, dist_a); 
	dijkstra(b, dist_b); 

	memset(memo, -1, sizeof memo);  
	ll ans = dist_a[b]; 
	for (int u = 1; u <= n; u++) {
		minimize(ans, dist_a[u] + dp_b(u)); 
	}

	memset(memo, -1, sizeof memo);  
	for (int u = 1; u <= n; u++) {
		minimize(ans, dist_b[u] + dp_a(u)); 
	}

	cout << ans << '\n'; 
}

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