Submission #400521

#	Time	Username	Problem	Language	Result	Execution time	Memory
400521		Cantfindme	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2090 ms	262148 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 totaldist;

bool check(int a, int b, int c, int arrs[], int arre[]) {
	if (arrs[a] + arre[b] + c == totaldist) return true;
	return false;
}

void findans(int st, int ep, int arrs[], int arre[]) {
	priority_queue <pi, vector<pi>, greater<pi>> pq;
	
	for (int i =1;i<=n;i++) dp[i] = INF;
	
	//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,arrs,arre)) continue;
			
			dp[i] = min({dp[i], dp[x], dist[0][i]});
			pq.push(pi(arrs[i],i));
		}
	}
}

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, dist[2],dist[3]);
	findans(T,S, dist[3],dist[2]);

	cout << ans;
}

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