Submission #367706

#	Time	Username	Problem	Language	Result	Execution time	Memory
367706		8e7	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	475 ms	25052 KiB

commuter_pass

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#define maxn 100005
#define mod 1000000007
#define ll long long
#define pii pair<int, ll>
#define ff first
#define ss second
using namespace std;
const ll inf = 1LL<<60;
vector<pii> adj[maxn];
vector<int> dag[maxn];
bool poss[maxn];
int deg[maxn];
ll ms[maxn], mu[maxn], mv[maxn], dp[maxn], dp2[maxn];

inline bool cmp(const pii &a, const pii &b) {
	return a.ss > b.ss;
}
priority_queue<pii, vector<pii>, bool (*) (const pii&, const pii&) > pq(cmp);

void dijkstra(int s, int n, ll mind[]) {
	for (int i = 1;i <= n;i++) mind[i] = inf;
	mind[s] = 0;
	pq.push(make_pair(s, 0));
	while (pq.size()) {
		int cur = pq.top().ff;
		ll dis = pq.top().ss;
		pq.pop();
		if (dis != mind[cur]) continue;
		for (auto v:adj[cur]) {
			ll nd = dis + v.ss;
			if (nd < mind[v.ff]) {
				mind[v.ff] = nd;
				pq.push(make_pair(v.ff, nd));
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, S, T, U, V;
	cin >> n >> m >> S >> T >> U >> V;
	for (int i = 0;i < m;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
	dijkstra(S, n, ms);
	dijkstra(U, n, mu);
	dijkstra(V, n, mv);
	poss[T] = true;
	for (int i = 1;i <= n;i++) {
		for (auto ed:adj[i]) {
			if (ms[i] + ed.ss == ms[ed.ff]) {
				dag[ed.ff].push_back(i);
				deg[i]++;//reverse degree
			}
		}
	}
	queue<int> que;
	for (int i = 1;i <= n;i++) {
		dp[i] = dp2[i] = inf;
		if (deg[i] == 0) que.push(i);
	}
	dp[T] = mv[T], dp2[T] = mu[T];
	ll ans = mu[V];
	while (que.size()) {
		int cur = que.front();
		if (poss[cur]) {
			//cout << cur << " " << endl;
			dp[cur] = min(dp[cur], mv[cur]);
			dp2[cur] = min(dp2[cur], mu[cur]);
		}
		ans = min(ans, min(mu[cur] + dp[cur], mv[cur] + dp2[cur]));
		que.pop();
		for (int v:dag[cur]) {
			poss[v] |= poss[cur];
			if (poss[cur]) {
				dp[v] = min(dp[v], dp[cur]);
				dp2[v] = min(dp2[v], dp2[cur]);
			}
			if (--deg[v] == 0) {
				que.push(v);
			}
		}
	}
	cout << ans << "\n";
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1


6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
 */

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