제출 #1115701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115701		staszic_ojuz	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	58 ms	11080 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 100001;

int n, m, s, t, u, v;

vector<pair<int, ll>> sasiedzi[MAXN];

ll odl_od_s[MAXN];
int ojciec_dijkstra[MAXN];
bool odwiedzone[MAXN];
vector<int> sciezka;
ll odl_od_u[MAXN];

void dijkstra_z_u_do_v() {
	priority_queue<pair<ll, int>> kopiec;
	kopiec.push({0, u});
	
	for (int i = 1; MAXN > i; i++) {
		odwiedzone[i] = false;
	}
	pair<ll, int> p1;
	ll aktl_koszt;
	int aktl_v;
	
	while (!kopiec.empty()) {
		p1 = kopiec.top();
		kopiec.pop();
		aktl_koszt = -p1.first;
		aktl_v = p1.second;
		if (odwiedzone[aktl_v]) continue;
		odwiedzone[aktl_v] = true;
		odl_od_u[aktl_v] = aktl_koszt;
		for (pair<int, ll> sasd: sasiedzi[aktl_v]) {
			if (odwiedzone[sasd.first]) continue;
			kopiec.push({-(aktl_koszt + sasd.second), sasd.first});
		}
	}
	cout << odl_od_u[v];
}
	

void dijkstra_z_s() {
	priority_queue<pair<ll, pair<int, int>>> kopiec;
	kopiec.push({0, {s, 0}});
	
	pair<ll, pair<int, int>> p1;
	ll aktl_koszt;
	int aktl_v, aktl_ojciec_dijkstra;
	
	while (!kopiec.empty()) {
		p1 = kopiec.top();
		kopiec.pop();
		aktl_koszt = -p1.first;
		aktl_v = p1.second.first;
		aktl_ojciec_dijkstra = p1.second.second;
		if (odwiedzone[aktl_v]) continue;
		odwiedzone[aktl_v] = true;
		odl_od_s[aktl_v] = aktl_koszt;
		ojciec_dijkstra[aktl_v] = aktl_ojciec_dijkstra;
		for (pair<int, ll> sasd: sasiedzi[aktl_v]) {
			if (odwiedzone[sasd.first]) continue;
			kopiec.push({-(aktl_koszt + sasd.second), {sasd.first, aktl_v}});
		}
	}
}
		
		
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> s >> t >> u >> v;
	
	int w1, w2;
	ll w3;
	
	for (int i = 0; m > i; i++) {
		cin >> w1 >> w2 >> w3;
		sasiedzi[w1].push_back({w2, w3});
	}
	
	dijkstra_z_s();
	
	/*for (int i = 1; n >= i; i++) {
		cout << i << " odl od s " << odl_od_s[i] << " ojciec dijkstra " << ojciec_dijkstra[i] << "\n";
	}*/
	int aktl_v = t;
	while (aktl_v) {
		sciezka.push_back(aktl_v);
		aktl_v = ojciec_dijkstra[aktl_v];
	}
	int aktl_ind = int(sciezka.size()) - 1;
	while (aktl_ind) {
		for (int i = 0; int(sasiedzi[sciezka[aktl_ind]].size()) > i; i++) {
			if (sasiedzi[sciezka[aktl_ind]][i].first == sciezka[aktl_ind - 1]) {
				sasiedzi[sciezka[aktl_ind]][i].second = 0;
				aktl_ind--;
				break;
			}
		}
	}
	dijkstra_z_u_do_v();
	return 0;
}

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