제출 #1129431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129431		ChuanChen	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	591 ms	28004 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];
int pai[lim];
void dijkS(){
	set<pair<ll, 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);
				pai[v] = no;
			}
		}
	}
}

void dijkT(){
	int no = T;
	while(no != S){
		int anc = pai[no];
		for(int i = 0; i < adj[no].size(); i++){
			if(adj[no][i] == anc){
				weight[no][i] = 0;
				break;
			}
		}
		for(int i = 0; i < adj[anc].size(); i++){
			if(adj[anc][i] == no){
				weight[anc][i] = 0;
				break;
			}
		}
		no = anc;
	}
}

void dijkV(){
	set<pair<ll, 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);
			}
		}
	}
}
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, i);
	}

	//S -> T
	dijkS();
	dijkT();

	dijkV();

	cout << dV[U] << '\n';
}

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