Submission #650035

#	Time	Username	Problem	Language	Result	Execution time	Memory
650035		zxcvbnm	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2052 ms	16556 KiB

commuter_pass

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

constexpr int nax = 1e5 + 5;
constexpr ll INF = 1e15 + 5;
vector<pair<int, int>> adj[nax];

ll dist[nax][4];
ll ans = INF;
int n, m;

void dijkstra(int s, int idx) {
	dist[s][idx] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	q.push({0, s});
	
	while(!q.empty()) {
		auto v = q.top();
		q.pop();
		
		if (v.first != dist[v.second][idx]) continue;
		
		for(auto u : adj[v.second]) {
			ll curr = v.first + u.second;
			if (curr < dist[u.first][idx]) {
				dist[u.first][idx] = curr;
				q.push({dist[u.first][idx], u.first});
			} 
		}
	}
}

struct S {
	ll dist;
	int v, type;
	bool operator<(const S& other) const {
		return array<ll, 3>{dist, v, type} > 
		array<ll, 3>{other.dist, other.v, other.type};
	}
};

void go(int start, int end, int c1, int c2) {
	ll dp[nax][3];
	for(int i = 0; i < nax; i++) {
		for(int j = 0; j < 3; j++) {
			dp[i][j] = INF;
		}
	}
	
	dp[start][0] = 0;
	dp[start][1] = dist[start][2];
	dp[start][2] = dist[start][3];
	priority_queue<S> q;
	q.push({dp[start][0], start, 0});
	q.push({dp[start][1], start, 1});
	
	while(!q.empty()) {
		auto v = q.top();
		q.pop();
		
		//cout << v.v << " " << v.type << " " << v.dist << "\n";
		v.dist = min(v.dist, dp[v.v][v.type]);
		//if (v.dist != dp[v.v][v.type]) continue;
		
		if (v.type == 0) {
			ll curr = v.dist + dist[v.v][2];
			if (dp[v.v][1] > curr) {
				dp[v.v][1] = curr;
				q.push({dp[v.v][1], v.v, 1});
			}
		}
		else if (v.type == 1) {
			ll curr = v.dist + dist[v.v][3];
			if (dp[v.v][2] > curr) {
				dp[v.v][2] = curr;
			}
		}
		
		for(auto u : adj[v.v]) {
			ll w = dist[v.v][0] + u.second + dist[u.first][1];
			if (w != dist[end][0]) {
				continue;
			}
			
			//cout << v.v << "->" << u.first << " " << v.type << " " << v.dist << ": " << w << " " << dist[end][0] << "\n";

			if (dp[u.first][v.type] > v.dist) {
				dp[u.first][v.type] = v.dist;
				//cout << u.first << " " << v.type << ": " << dp[u.first][v.type] << "\n";
				q.push({dist[u.first][v.type], u.first, v.type});
			}
		}
	}
	
	for(int i = 1; i <= n; i++) {
		//cout << dp[i][2] << "\n";
		ans = min(dp[i][2], ans);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	int start, end, c1, c2;
	cin >> start >> end >> c1 >> c2;
	
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j < 4; j++) {
			dist[i][j] = INF;
		}
	}
	
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	
	dijkstra(start, 0);
	dijkstra(end, 1);
	dijkstra(c1, 2);
	dijkstra(c2, 3);
	ans = dist[c2][2];
	
	//cout << dist[end][0] << "\n";
	// go(start, end, c2, c1)
	go(start, end, c1, c2);
	cout << ans << "\n";
}

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