Submission #400528

#	Time	Username	Problem	Language	Result	Execution time	Memory
400528		Cantfindme	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	372 ms	23488 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
 
const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

int n, e;
int S,T,U,V;
vector <pi> adjlist[maxn];
int dist[4][maxn];

void dijkstra(int st, int arr[]) {
	priority_queue <pi, vector<pi>, greater<pi>> pq;
	
	pq.push(pi(0,st));
	arr[st] = 0;
	
	while (!pq.empty()) {
		auto [d,x] = pq.top(); pq.pop();
		if (arr[x] != d) continue;
		
		for (auto [i,c] : adjlist[x]) {
			if (arr[i] == -1 or arr[i] > c + d) {
				arr[i] = c + d;
				pq.push(pi(arr[i],i));
			}
		}
	}
}

int ans = INF; 
int dp[maxn]; //best
int vis[maxn];
int totaldist;

bool check(int a, int b, int c, int XX) {
	if (XX == 0 and dist[2][a] + dist[3][b] + c == totaldist) return true;
	if (XX == 1 and dist[3][a] + dist[2][b] + c == totaldist) return true;
	return false;
}

void findans(int st, int ep, int XX) {
	priority_queue <pi, vector<pi>, greater<pi>> pq;
	
	for (int i =1;i<=n;i++) dp[i] = INF;
	memset(vis,0,sizeof vis);
	
	//cout << "\nNEW\n";
	pq.push(pi(0,st));
	dp[st] = dist[0][st];
	
	while (!pq.empty()) {
		auto [d,x] = pq.top(); pq.pop();
		
		ans = min(ans, dist[1][x] + dp[x]);
		//cout << x << " " << dp[x] << " " << ans << "\n";
		
		for (auto [i,c] : adjlist[x]) {
			if (!check(x,i,c,XX)) continue;
			
			dp[i] = min({dp[i], dp[x], dist[0][i]});
			if (!vis[i]) {
				if (XX == 0) pq.push(pi(dist[2][i],i));
				else pq.push(pi(dist[3][i],i));
				vis[i] = 1;
			}
		}
	}
}

int32_t main() {
	FAST
	cin >> n >> e;
	cin >> S >> T;
	cin >> U >> V;
	for (int i =0;i<e;i++) {
		int a,b,c; cin >> a >> b >> c;
		adjlist[a].push_back(pi(b,c));
		adjlist[b].push_back(pi(a,c));
	}
	
	memset(dist,-1,sizeof dist);
	dijkstra(U, dist[0]);
	dijkstra(V, dist[1]);
	dijkstra(S, dist[2]);
	dijkstra(T, dist[3]);
	
	totaldist = dist[2][T];
	ans = dist[0][V];

	findans(S,T, 0);
	findans(T,S, 1);

	cout << ans;
}

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