Submission #504212

#	Time	Username	Problem	Language	Result	Execution time	Memory
504212		ojuzuser12	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	412 ms	262152 KiB

commuter_pass

// https://oj.uz/problem/view/JOI18_commuter_pass
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll, ll, vector<ll>> tll;

int main() {
	ll N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V;
	vector<vector<pair<ll, ll>>> adj(N + 1);
	for(int i = 0; i < M; i++) {
		ll a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}

	priority_queue<tll, vector<tll>, greater<tll>> q;
	vector<ll> empty; empty.push_back({S});
	tll start = make_tuple(0, S, empty);
	q.push(start);

	vector<vector<ll>> paths;
	ll min_cost[N + 1];
	for(int i = 1; i <= N; i++) {
		min_cost[i] = LLONG_MAX;
	}
	while(!q.empty()) {
		tll curr = q.top();
		q.pop();
		ll cost = get<0>(curr), u = get<1>(curr);
		if(cost > min_cost[u]) continue;
		vector<ll> path = get<2>(curr);
		if(u == T) paths.push_back(path);

		for(pair<ll, ll> p : adj[u]) {
			ll v = p.first, new_cost = p.second;
			if(min_cost[v] >= cost + new_cost) {
				if(v == T) paths.clear();
				min_cost[v] = cost + new_cost;
				path.push_back(v);
				q.push(make_tuple(cost + new_cost, v, path));
				path.pop_back();
			}
		}
	}

	ll ans = LLONG_MAX;
	for(vector<ll> path : paths) {
		vector<vector<pair<ll, ll>>> adj2 = adj;
		for(int i = 0; i < path.size() - 1; i++) {
			for(int j = 0; j < adj2[path[i]].size(); j++) {
				if(adj2[path[i]][j].first == path[i + 1]) {
					adj2[path[i]][j].second = 0;
				}
			}
			for(int j = 0; j < adj2[path[i + 1]].size(); j++) {
				if(adj2[path[i + 1]][j].first == path[i]) {
					adj2[path[i + 1]][j].second = 0;
				}
			}
		}
		for(int i = 1; i <= N; i++) {
			min_cost[i] = LLONG_MAX;
		}

		priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q2;
		q2.push({0, U});
		while(!q2.empty()) {
			ll cost = q2.top().first, u = q2.top().second;
			q2.pop();
			if(cost > min_cost[u]) continue;
			for(pair<ll, ll> p : adj2[u]) {
				ll v = p.first, new_cost = p.second;
				if(min_cost[v] > cost + new_cost) {
					min_cost[v] = cost + new_cost;
					q2.push({cost + new_cost, v});
				}
			}
		}
		ans = min(ans, min_cost[V]);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0; i < path.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int j = 0; j < adj2[path[i]].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(int j = 0; j < adj2[path[i + 1]].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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