Submission #1043593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043593		VectorLi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	417 ms	21716 KiB

commuter_pass

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = (int) 1E5;
const long A = numeric_limits<long>::max();

int n, m;
vector<pair<int, int>> e[N];

vector<long> Dijkstra(int i) {
	vector<long> d(n, A);
	set<pair<long, int>> s;
	
	d[i] = 0;
	s.insert({0, i});
	
	while (not s.empty()) {
		int u = s.begin() -> second;
		s.erase(s.begin());
		
		for (auto [v, w] : e[u]) {
			if (d[v] > d[u] + w) {
				s.erase({d[v], v});
				d[v] = d[u] + w;
				s.insert({d[v], v});
			}
		}
	}
	
	return d;
}

int s, t;
int x, y;
vector<long> d[4];

long c;

void DP(int i) {
	vector<long> dd(n, A);
	vector<long> g(n);
	set<pair<long, int>> s;
	
	dd[i] = 0;
	g[i] = d[2][i];
	s.insert({0, i});
	// 如果一个节点在 s 到 t 的最短路上，我们就可以用来更新
	// i 节点不是 s 就是 t，可以用来更新 
	// g 数组存储节点 x 到所有 i 之前的节点的最短路径，起始节点只有一个选项 
	c = min(c, g[i] + d[3][i]);
	
	while (not s.empty()) {
		int u = s.begin() -> second;
		s.erase(s.begin());
		
		for (auto [v, w] : e[u]) {
			if (dd[v] > dd[u] + w) {
				s.erase({dd[v], v});
				dd[v] = dd[u] + w;
				// 此时 v 还只有 u 一个可以到达的前驱，DP 
				g[v] = min(d[2][v], g[u]);
				s.insert({dd[v], v}); 
			} else if (dd[v] == dd[u] + w) {
				// 由于边权正，所有 v 的前驱都会枚举到
				g[v] = min(g[v], g[u]);
				
			}
		}
	}
	
	for (int u = 0; u < n; u++) {
		if (d[0][u] + d[1][u] == d[0][t]) {
			c = min(c, g[u] + d[3][u]);
		} 
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	cin >> s >> t;
	cin >> x >> y;
	s = s - 1, t = t - 1;
	x = x - 1, y = y - 1;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u = u - 1, v = v - 1;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	
	d[0] = Dijkstra(s);
	d[1] = Dijkstra(t);
	d[2] = Dijkstra(x);
	d[3] = Dijkstra(y);
	c = d[2][y];
	DP(s);
	DP(t);
	cout << c << "\n";
	
	return 0;
}

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