Submission #332847

#	Time	Username	Problem	Language	Result	Execution time	Memory
332847		parsabahrami	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	461 ms	41080 KiB

commuter_pass

#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, MOD = 1e9 + 7;
ll dist[4][N], dp[2][N], M[N], X[N], n, m, R = 1e18, B, E, U, V;
vector<pii> adj[N]; vector<int> out[N], in[N];

void dijk(int S, int t) {
	fill(dist[t], dist[t] + N, 1e18);
	dist[t][S] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.push({dist[t][S], S});
	while (SZ(pq)) {
		int v = pq.top().S; pq.pop();
		for (pii u : adj[v]) {
			if (dist[t][u.F] > dist[t][v] + u.S) {
				dist[t][u.F] = dist[t][v] + u.S;
				pq.push({-dist[t][u.F], u.F});
			}
		}
	}
}

void add_edge(int u, int v) {
	out[u].push_back(v);
	in[v].push_back(u);
}

void DFS(int v) {
	M[v] = 1;
	for (int u : out[v]) {
		if (!M[u]) DFS(u);
		dp[0][v] = min(dp[0][v], dp[0][u]);
	}
}

void SFD(int v) {
	M[v] = 1;
	for (int u : in[v]) {
		if (!M[u]) SFD(u);
		dp[1][v] = min(dp[1][v], dp[1][u]);
	}
}

int main() {
	scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &B, &E, &U, &V);
	for (int i = 1; i <= m; i++) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dijk(B, 0);
	dijk(E, 1);
	dijk(U, 2);
	dijk(V, 3);
	for (int i = 1; i <= n; i++) {
		if (dist[0][i] + dist[1][i] == dist[0][E]) X[i] = 1;
		for (pii u : adj[i]) {
			if (dist[0][i] + u.S + dist[1][u.F] == dist[0][E]) {
				add_edge(i, u.F);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[0][i] = dp[1][i] = dist[3][i];
	}
	for (int i = 1; i <= n; i++) {
		if (X[i] && !M[i]) DFS(i);
	}
	fill(M, M + N, 0);
	for (int i = 1; i <= n; i++) {
		if (X[i] && !M[i]) SFD(i);
	}/*
	for (int i = 1; i <= n; i++) {
        printf("%lld %lld\n", dp[0][i], dp[1][i]);
    }*/
	for (int i = 1; i <= n; i++) {
		if (X[i]) {
			R = min(R, min(dp[0][i], dp[1][i]) + dist[2][i]);
		}
	}
	printf("%lld\n", min(R, dist[2][V]));
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &B, &E, &U, &V);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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