Submission #833502

#	Time	Username	Problem	Language	Result	Execution time	Memory
833502		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	490 ms	21192 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, int> pii;

#define For(i, n) for (int i = 0; i < n; i++)
#define Each(x, v) for (auto x : v)
#define pb push_back
#define fi first
#define se second

const ll INF = LLONG_MAX;
const int MAXN = 1e5;
int N, M, S, T, U, V;
vector <pii> adjList[MAXN];
set <pii> khusus;

void StoT() {
	priority_queue < pii, vector <pii>, greater <pii> > pq;
	pq.push({0, S});
	int fr[N];
	ll distance[N];
	For (i, N) fr[i] = -1, distance[i] = INF;
	distance[S] = 0;
	while (!pq.empty()) {
		ll dis = pq.top().fi;
		int x = pq.top().se;
		pq.pop();
		Each (next, adjList[x]) {
			if (distance[next.fi] <= dis + next.se) continue;
			distance[next.fi] = dis + next.se;
			fr[next.fi] = x;
			pq.push({dis + next.se, next.fi});
		}
	}
	int cur = T;
	while (cur != S) {
		if (fr[cur] == -1) break;
		khusus.insert({cur, fr[cur]});
		cur = fr[cur];
	}
//	cout << "khusus\n";
//	Each (x, khusus) {
//		cout << x.fi << " " << x.se << endl;
//	}
}

void UtoV() {
	priority_queue < pii, vector <pii>, greater <pii> > pq;
	pq.push({0, U});
	int fr[N];
	ll distance[N];
	For (i, N) distance[i] = INF;
	distance[U] = 0;
	while (!pq.empty()) {
		ll dis = pq.top().fi;
		int x = pq.top().se;
		pq.pop();
		Each (next, adjList[x]) {
			if (khusus.count({x, next.fi}) || khusus.count({next.fi, x})) {
				if (distance[next.fi] <= dis) continue;
				distance[next.fi] = dis;
				pq.push({dis, next.fi});
			}
			else {
				if (distance[next.fi] <= dis + next.se) continue;
				distance[next.fi] = dis + next.se;
				pq.push({dis + next.se, next.fi});
			}
		}
	}
//	for (int i = 0; i < N; i++) {
//		cout << distance[i] << " "; 
//	} cout << endl;
	cout << distance[V] << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> N >> M >> S >> T >> U >> V;
	S--, T--, U--, V--;
	For (i, M) {
		int A, B, C; cin >> A >> B >> C;
		A--, B--;
		adjList[A].pb({B, C});
		adjList[B].pb({A, C});
	}
	// dijkstra dari S sampai T
	StoT();
	// dijkstra dari U ke V
	UtoV();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void UtoV()':
commuter_pass.cpp:51:6: warning: unused variable 'fr' [-Wunused-variable]
   51 |  int fr[N];
      |      ^~

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