Submission #330373

#	Time	Username	Problem	Language	Result	Execution time	Memory
330373		Seanliu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	425 ms	35780 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
#define int long long int
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxN = 2e5 + 326, INF = 1e17;
int N, M, S, T, U, V, u, v, w, fromS[maxN], fromU[maxN], toT[maxN], toV[maxN], minToV[maxN], ans = INF, deg[maxN], dp1[maxN], dp2[maxN];
bool inRoute[maxN];
vector<int> chi[maxN];
queue<int> que;

struct Dijkstra{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	int dist[maxN], N;
	bool vis[maxN];
	vector<pii> adj[maxN];
	Dijkstra(){}
	Dijkstra(int N): N(N){}

	inline void addEdge(int u, int v, int w){
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	inline void run(int s){
		fill(vis, vis + N + 1, false);
		fill(dist, dist + N + 1, INF);
		pq = priority_queue<pii, vector<pii>, greater<pii>>();
		dist[s] = 0;
		pq.push({0, s});
		while(pq.size()){
			auto [d, u] = pq.top();
			pq.pop();
			if(vis[u]) continue;
			vis[u] = true;
			for(auto [v, w] : adj[u]){
				if(vis[v]) continue;
				if(w + d < dist[v]){
					dist[v] = w + d;	
					pq.push({w + d, v});
				}
			}
		}
	}
} sp;

signed main(){
	ericxiao
	cin >> N >> M >> S >> T >> U >> V;
	sp = Dijkstra(N);
	for(int i = 0; i < M; i++){
		cin >> u >> v >> w;
		sp.addEdge(u, v, w);
	}
	sp.run(S);
	for(int i = 1; i <= N; i++) fromS[i] = sp.dist[i];
	/*
	for(int i = 1; i <= N; i++){
		cout << S << " - " << i << " = " << fromS[i] << endl;
	}
	*/
	sp.run(T);
	for(int i = 1; i <= N; i++) toT[i] = sp.dist[i];
	sp.run(V);
	for(int i = 1; i <= N; i++) toV[i] = sp.dist[i];	
	sp.run(U);
	for(int i = 1; i <= N; i++) fromU[i] = sp.dist[i];
	ans = toV[U];
	for(int i = 1; i <= N; i++){
		for(auto [u, w] : sp.adj[i]){
			if(fromS[i] + w + toT[u] == toT[S]){
				//cout << i << " - " << u << " lies on a path from " << S << " to " << T << endl;
				inRoute[i] = inRoute[u] = true;
				chi[u].push_back(i);
				deg[i]++;
			}
		}
	}
	for(int i = 1; i <= N; i++) if(inRoute[i] && !deg[i]) que.push(i);
	fill(dp1, dp1 + N + 1, INF);
	fill(dp2, dp2 + N + 1, INF);
	while(que.size()){
		int f = que.front();
		que.pop();
		dp1[f] = min(dp1[f], toV[f]);
		dp2[f] = min(dp2[f], fromU[f]);
		//cout << "toV min of childs = " << dp1[f] << ", fromU min of childs = " << dp2[f] << endl;
		ans = min(ans, fromU[f] + dp1[f]);
		ans = min(ans, toV[f] + dp2[f]);
		for(int x : chi[f]){
			dp1[x] = min(dp1[x], dp1[f]);
			dp2[x] = min(dp2[x], dp2[f]);
			deg[x]--;
			if(!deg[x]){
				que.push(x);
			}
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In member function 'void Dijkstra::run(long long int)':
commuter_pass.cpp:39:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |    auto [d, u] = pq.top();
      |         ^
commuter_pass.cpp:43:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |    for(auto [v, w] : adj[u]){
      |             ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |   for(auto [u, w] : sp.adj[i]){
      |            ^

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