Submission #1302146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302146		duyanhchupapi	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	161 ms	28944 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1e5 + 5;
const ll inf = 1e18;
int n, m, uu, vv, s, t, deg[N], topo[N];
vector <pair<int, int>> g[N];
vector <int> adj[N], radj[N];
ll dist[3][N], dp[N];
bool vis[N];

void dijkstra(int u, int id) {
	fill(dist[id], dist[id] + n + 1, inf);
	dist[id][u] = 0;
	priority_queue <pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> pq;
	pq.emplace(0, u);
	
	while (!pq.empty()) {
		int u = pq.top().second;
		ll du = pq.top().first;
		pq.pop();
		if (du != dist[id][u]) continue;
		
		for (pair <int, int> P : g[u]) {
			int v = P.first, w = P.second;
			if (du + w < dist[id][v]) {
				dist[id][v] = du + w;
				pq.emplace(dist[id][v], v);
			} 
		}
	}
}

vector <int> luu;
void dfs(int u) {
	luu.push_back(u);
	vis[u] = 1;
	for (pair <int, int> P : g[u]) {
		int v = P.first, w = P.second;
		if (dist[0][u] == dist[0][v] + w) {
			deg[u]++;
			adj[v].push_back(u);
			radj[u].push_back(v);
			if (!vis[v]) dfs(v);
		}
	}
}

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("test.inp", "r", stdin);
	// freopen(".OUT", "w", stdout);
	cin >> n >> m >> s >> t >> uu >> vv;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	
	dijkstra(s, 0);
	dijkstra(uu, 1);
	dijkstra(vv, 2);
	dfs(t);
	
	queue <int> q;
	int idd = 0;
	ll ans = dist[1][vv];
	for (int u : luu) if (deg[u] == 0) q.push(u);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		topo[++idd] = u;
		for (int v : adj[u]) if (--deg[v] == 0) q.push(v);
	}
	
	for (int i=idd;i>=1;--i) {
		int u = topo[i];
		dp[u] = dist[2][u];
		for (int v : adj[u]) dp[u] = min(dp[u], dp[v]);
		ans = min(ans, dist[1][u] + dp[u]);	
	}
	
	fill(dp, dp + idd + 1, 0);
	
	for (int i=1;i<=idd;++i) {
		int u = topo[i];
		dp[u] = dist[2][u];
		for (int v : radj[u]) dp[u] = min(dp[u], dp[v]);
		ans = min(ans, dist[1][u] + dp[u]);
	}
	
	cout << ans;
}

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