Submission #1130766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130766		ChuanChen	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	742 ms	33708 KiB

commuter_pass

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

typedef long long ll;
const int lim = 1e5+5;
const ll inf = 1e18;

int n, m, S, T, U, V;
ll ans = inf;
//ARESTAS
struct Edge{ int a, b, c; };
vector<Edge> edges;
vector<int> adj[lim], weight[lim];
void addEdge(int a, int b, int c){
	edges.push_back({a, b, c});
	adj[a].push_back(b);
	adj[b].push_back(a);
	weight[a].push_back(c);
	weight[b].push_back(c);
}
//DIJK FOR MIN_PATHS
ll d[4][lim];
void dijk(int r){
	set<pair<ll, int>> can;
	for(int i = 1; i <= n; i++) d[r][i] = inf;
	if(r == 0) d[r][S] = 0;
	else if(r == 1) d[r][T] = 0;
	else if(r == 2) d[r][U] = 0;
	else if(r == 3) d[r][V] = 0;

	for(int i = 1; i <= n; i++) can.emplace(d[r][i], i);

	while(!can.empty()){
		int no = can.begin()->second;
		can.erase(can.begin());
		for(int i = 0; i < adj[no].size(); i++){
			int v = adj[no][i], p = weight[no][i];
			if(d[r][v] > d[r][no] + p){
				can.erase({d[r][v], v});
				d[r][v] = d[r][no] + p;
				can.emplace(d[r][v], v);
			}
		}
	}
}
//DAGs
vector<int> dag[2][lim];
ll dpU[2][lim], dpV[2][lim];
int ing[2][lim];

void solve(int r){
	queue<int> can;

	for(int i = 1; i <= n; i++){
		if(ing[r][i] == 0) can.push(i);
	}

	while(!can.empty()){
		int no = can.front();
		can.pop();
		dpU[r][no] = min(dpU[r][no], d[2][no]);
		dpV[r][no] = min(dpV[r][no], d[3][no]);

		if(dag[r][no].empty()) continue;
		for(int v : dag[r][no]){
			ing[r][v]--;
			if(ing[r][v] == 0) can.push(v);

			if(r == 0){
				dpU[0][v] = min(dpU[0][v], dpU[0][no]);
				dpV[1][v] = min(dpV[1][v], dpV[1][no]);
			}
			else{
				dpU[1][v] = min(dpU[1][v], dpU[1][no]);
				dpV[0][v] = min(dpV[0][v], dpV[0][no]);
			}
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	cin >> S >> T >> U >> V;

	for(int i = 1; i <= m; i++){
		int a, b, c; cin >> a >> b >> c;
		addEdge(a, b, c);
	}

	for(int i = 0; i < 4; i++) dijk(i);

	for(Edge &e : edges){
		if(d[0][e.a] + e.c + d[1][e.b] == d[0][T]){
			dag[0][e.a].push_back(e.b); ing[0][e.b]++;
			dag[1][e.b].push_back(e.a); ing[1][e.a]++;
		}
		if(d[0][e.b] + e.c + d[1][e.a] == d[0][T]){
			dag[1][e.a].push_back(e.b); ing[1][e.b]++;
			dag[0][e.b].push_back(e.a); ing[0][e.a]++;
		}
	}

	for(int i = 1; i <= n; i++)	dpU[0][i] = dpV[0][i] = dpU[1][i] = dpV[1][i] = inf;
	solve(0);
	solve(1);

	ans = d[2][V];
	for(int i = 1; i <= n; i++)
		ans = min({ans, dpU[0][i]+dpV[0][i], dpU[1][i]+dpV[1][i]});
	cout << ans << '\n';
}

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