Submission #1130433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130433		lucaskojima	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	300 ms	327680 KiB

commuter_pass

// subtask 3
#include "bits/stdc++.h"
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int n, m; cin >> n >> m;
	int s, t, u, v; cin >> s >> t >> u >> v;

	using pll = pair<ll, ll>;
	vector<vector<pll>> adj(n + 1);

	for (int i = 0; i < m; i++) {
		int a, b; ll c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}

	vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, LINF));
	vector<vector<int>> vis(n + 1, vector<int>(n + 1));

	auto dijkstra = [&](int s) -> void {
		dist[s][s] = 0LL;

		for (int _ = 0; _ < n; _++) {
			int x = -1;
			for (int i = 1; i <= n; i++)
				if (vis[s][i] == 0 && (x == -1 || dist[s][i] < dist[s][x]))
					x = i;

			vis[s][x] = 1;
		 	ll d = dist[s][x];
			for (auto [k, dd] : adj[x])
				if (d + dd < dist[s][k])
					dist[s][k] = d + dd;
		}
	};

	for (int i = 1; i <= n; i++)
		dijkstra(i);

	auto commuter = [&](int x, int y) -> bool {
		return dist[s][x] + dist[x][y] + dist[y][t] == dist[s][t];
	};

	ll ans = dist[u][v];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (commuter(i, j))
				ans = min({ans, dist[u][i] + dist[j][v], dist[u][j] + dist[i][v]});

	cout << ans << nl;
	return 0;
}

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