제출 #1087355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087355		nguyenkhangninh99	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	385 ms	31600 KiB

commuter_pass

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

#define int long long
#define fi first
#define se second
#define pii pair<int, int>

const int maxn = 1e5 + 5;

vector<pii> adj[maxn];
int du[maxn], dv[maxn], dist[maxn], dp[2][maxn], ans;
bool vis[maxn];
//dijkstra 1 tinh du (du[i] = shortest path tu u toi i) tuong tu voi dv;

void dijkstra1(int start, int arr[]) {
	for(int i = 0; i < maxn; i++) vis[i] = false;

	priority_queue<pair<int, int>> pq;
	pq.push({0, start});
	while (!pq.empty()) {
		int w = pq.top().fi, u = pq.top().se;
		pq.pop();

		if (!vis[u]) {
			arr[u] = -w;
			vis[u] = true;
			for (pii v: adj[u]) pq.push({w - v.se, v.fi});
		}
	}
}

void dijkstra2(int start, int end) {
	for(int i = 0; i < maxn; i++){
        vis[i] = false;
        dp[0][i] = dp[1][i] = 1e18;
    }


	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({0, {start, 0}});

    //dung dijkstra duyet qua shortest path s -> t va t -> s

    //goi dp[0][i] la shortest path khi xoa 1 vai canh cua shortest path tu s => t hoac t => s va tu u => i
    //ket qua la min du[u](di tu u-> i) hoac xoa canh par - u vi nam tren duong di ngan nhat
	while (!pq.empty()) {
		int c = pq.top().fi, u = pq.top().se.fi, par = pq.top().se.se;
		pq.pop();

		if (!vis[u]) {
			vis[u] = true;
			dist[u] = -c;
			dp[0][u] = min(du[u], dp[0][par]);
			dp[1][u] = min(dv[u], dp[1][par]);
			for (pii v: adj[u]) pq.push({c - v.se, {v.fi, u}});
		}

        //neu ton tai 1 duong di khac toi u co bang do dai thi ta so sanh min va lay ket qua  
        else if (-c == dist[u]) {
			if (min(du[u], dp[0][par]) + min(dv[u], dp[1][par]) <= dp[0][u] + dp[1][u]) {
				dp[0][u] = min(du[u], dp[0][par]);
				dp[1][u] = min(dv[u], dp[1][par]);
			}
		}
	}

	ans = min(ans, dp[0][end] + dp[1][end]);
}

void solve(){
    int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;

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

	dijkstra1(u, du);
	dijkstra1(v, dv);

	ans = du[v];

	dijkstra2(s, t);
	dijkstra2(t, s);

	cout << ans;
}


 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t = 1;
    //cin >> t;
    while(t--) solve();
 
    //cout << (7 ^ 7);
 
}

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