제출 #1134786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134786		bozocode	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	363 ms	17164 KiB

commuter_pass

#include <bits/stdc++.h>
#define vec vector
#define long int64_t
using namespace std;

int N;
vec<vec<array<int, 2>>> rails;

vec<long> dijkstra(int source) {
	vec<long> cost(N, 1e18);
	cost[source] = 0;
    auto cmp = [&](const int& u, const int& v) {
        return cost[u] != cost[v] ? cost[u] < cost[v] : u < v;
    };
    set<int, decltype(cmp)> s(cmp);
	s.insert(source);
	while (!s.empty()) {
		int u = *s.begin();
		s.erase(s.begin());
		for (auto [v, c] : rails[u]) {
			if (c + cost[u] < cost[v]) {
				s.erase(v);
				cost[v] = c + cost[u];
				s.insert(v);
			}
		}
	}
	return cost;
}

vec<long> ucost, vcost;

int S, T;

long dpdijkstra(bool change) {
    if (change) { swap(S, T); }
    vec<long> uclose(N, 1e18), vclose(N, 1e18);
    for (int i = 0; i < N; i++) {
        uclose[i] = ucost[i];
        vclose[i] = vcost[i];
    }
	vec<long> cost(N, 1e18);
	cost[S] = 0;
    auto cmp = [&](const int& u, const int& v) {
        return cost[u] != cost[v] ? cost[u] < cost[v] : u < v;
    };
    set<int, decltype(cmp)> s(cmp);
	s.insert(S);
	while (!s.empty()) {
		int u = *s.begin();
		s.erase(s.begin());
		for (auto [v, c] : rails[u]) {
            if (c + cost[u] > cost[v]) { continue; }
			if (c + cost[u] < cost[v]) {
				s.erase(v);
				cost[v] = c + cost[u];
				uclose[v] = min(ucost[v], uclose[u]);
				vclose[v] = min(vcost[v], vclose[u]);
				s.insert(v);
			}
			if (min(ucost[v], uclose[u]) + min(vcost[v], vclose[u]) < uclose[v] + vclose[v]) {
				uclose[v] = min(ucost[v], uclose[u]);
				vclose[v] = min(vcost[v], vclose[u]);
			}
		}
	}
    return uclose[T] + vclose[T];
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	int M; cin >> N >> M;
	cin >> S >> T; S--; T--;
	int U, V; cin >> U >> V; U--; V--;
	rails.resize(N);
	for (int i = 0; i < M; i++) {
		int u, v, c; cin >> u >> v >> c; u--; v--;
		rails[u].push_back({v, c});
		rails[v].push_back({u, c});
	}

	ucost = dijkstra(U), vcost = dijkstra(V);
    long ans = ucost[V];
    ans = min(ans, dpdijkstra(false));
    ans = min(ans, dpdijkstra(true));
    cout << ans << endl;
}

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