Submission #1129430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129430		ChuanChen	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	1368 ms	22804 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;

// struct Edge{
// 	int a, b, c;
// };
// Edge edges[2*lim];
vector<int> adj[lim], weight[lim], idx[lim];
void addEdge(int a, int b, int c, int i){
	adj[a].push_back(b);
	adj[b].push_back(a);
	weight[a].push_back(c);
	weight[b].push_back(c);
	// idx[a].push_back(i);
	// idx[b].push_back(i);
}

ll dS[lim], dT[lim], dV[lim];

void dijkS(){
	set<pair<int, int>> can;
	for(int i = 1; i <= n; i++) dS[i] = inf;
	dS[S] = 0;
	for(int i = 1; i <= n; i++) can.emplace(dS[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(dS[v] > dS[no] + p){
				can.erase({dS[v], v});
				dS[v] = dS[no] + p;
				can.emplace(dS[v], v);
			}
		}
	}
}

void dijkT(){
	set<pair<int, int>> can;
	for(int i = 1; i <= n; i++) dT[i] = inf;
	dT[T] = 0;
	for(int i = 1; i <= n; i++) can.emplace(dT[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(dT[v] > dT[no] + p){
				can.erase({dT[v], v});
				dT[v] = dT[no] + p;
				can.emplace(dT[v], v);
			}
		}
	}
}

void dijkV(){
	set<pair<int, int>> can;
	for(int i = 1; i <= n; i++) dV[i] = inf;
	dV[V] = 0;
	for(int i = 1; i <= n; i++) can.emplace(dV[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(dV[v] > dV[no] + p){
				can.erase({dV[v], v});
				dV[v] = dV[no] + p;
				can.emplace(dV[v], v);
			}
			ans = min(ans, dS[v] + dV[v]);
		}
	}
}
int main(){
	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, i);
	}

	dijkS();
	dijkT();

	for(int i = 1; i <= n; i++){
		if(dT[i]+dS[i] == dT[S]) dS[i] = 0;
	}
	dijkV();

	cout << ans << '\n';
}

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