Submission #446725

#	Time	Username	Problem	Language	Result	Execution time	Memory
446725		zeyu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	681 ms	34416 KiB

commuter_pass

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
typedef pair<ll, int> pl;
int n, m, s, t, u, v;
vector<pl> graph[maxn];
vector<ll> dist;
vector<ll> du(maxn, 1ll << 50), dv(maxn, 1ll << 50);
vector<int> prv[maxn], nxt[maxn];
priority_queue< pl, vector<pl>, greater<pl> > pq;
vector<int> ind(maxn);
bool in[maxn];

void dijkstra(int x, bool z1, bool z2){
	dist.assign(maxn, 1ll << 50);
	dist[x] = 0;
	pq.push(make_pair(0, x));
	while(! pq.empty()){
		pl p = pq.top(); pq.pop();
		int y = p.second; ll d = p.first;
		if (d > dist[y]) continue;
		for (int i = 0; i < graph[y].size(); i ++){
			int to = graph[y][i].second;
			ll w = graph[y][i].first;
			if (w + d < dist[to]){
				dist[to] = w + d;
				pq.push(make_pair(dist[to], to));
				if (z1){
					prv[to].clear();
					prv[to].push_back(y);
				} else if (z2){
					nxt[to].clear();
					nxt[to].push_back(y);
				}
			} else if (w + d == dist[to]){
				if (z1) prv[to].push_back(y);
				else if (z2) nxt[to].push_back(y);
			}
		}
	}
}

void bfs(vector<ll> &dp1, vector<ll> &dp2, int st){
	queue<int> que;
	que.push(st);
	dp1[st] = dv[st];
	dp2[st] = du[st];
	while(! que.empty()){
		int p = que.front(); que.pop();
		in[p] = true;
		int sz = (st == s ? nxt[p].size() : prv[p].size());
		for (int i = 0; i < sz; i ++){
			int to = (st == s ? nxt[p][i] : prv[p][i]);
			dp1[to] = min(dp1[to], min(dp1[p], dv[to]));
			dp2[to] = min(dp2[to], min(dp2[p], du[to]));
			ind[to] --;
			if (ind[to] == 0) que.push(to);
		}
	}	
}

int main(){
	cin >> n >> m >> s >> t >> u >> v;
	s --; t --; u --; v --;
	for (int i = 0; i < m; i ++){
		int x, y; ll w;
		cin >> x >> y >> w;
		x --; y --;
		graph[x].push_back(make_pair(w, y));
		graph[y].push_back(make_pair(w, x));
	}
	dijkstra(s, true, false);
	dijkstra(t, false, true);
	dijkstra(u, false, false);
	du = dist;
	dijkstra(v, false, false);
	dv = dist;
	ll ans = dv[u];
	vector<ll> dp_fv(maxn, 1ll << 50), dp_bv(maxn, 1ll << 50), dp_fu(maxn, 1ll << 50), dp_bu(maxn, 1ll << 50);
	for (int i = 0; i < n; i ++){
		ind[i] = prv[i].size();
	}
	bfs(dp_fv, dp_fu, s);
	for (int i = 0; i < n; i ++){
		ind[i] = nxt[i].size();
	}
	bfs(dp_bv, dp_bu, t);
	for (int i = 0; i < n; i ++){
		if (in[i]){
			ans = min(ans, dp_fu[i] + dp_bv[i]);
			ans = min(ans, dp_fv[i] + dp_bu[i]);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, bool, bool)':
commuter_pass.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int i = 0; i < graph[y].size(); i ++){
      |                   ~~^~~~~~~~~~~~~~~~~

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