Submission #934376

#	Time	Username	Problem	Language	Result	Execution time	Memory
934376		SmuggingSpun	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	69 ms	13008 KiB

commuter_pass

#include<bits/stdc++.h>
#define taskname "commuterpass"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const ll INF = 1e18;
const int lim = 1e5 + 5;
vector<pair<int, int>>e[lim];
void dijkstra(int vertex, vector<ll>& d){
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>pq;
	pq.emplace(d[vertex] = 0, vertex);
	bitset<lim>vis;
	vis.reset();
	while(!pq.empty()){
		auto [w, u] = pq.top();
		pq.pop();
		if(!vis.test(u)){
			vis.set(u);
			for(auto& [v, edge_w] : e[u]){
				ll W = w + edge_w;
				if(W < d[v]){
					pq.emplace(d[v] = W, v);
				}
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b >> c;
		e[a].emplace_back(b, c);
		e[b].emplace_back(a, c);
	}
	vector<ll>d_s(n + 1, INF), d_u(n + 1, INF), d_v(n + 1, INF), dp_u(n + 1, INF), dp_v(n + 1, INF);
	dijkstra(s, d_s);
	dijkstra(u, d_u);
	dijkstra(v, d_v);
	ll ans = d_u[v];
	function<void(int)>dfs;
	dfs = [&] (int vertex){
		if(dp_u[vertex] != INF){
			return;
		}
		dp_u[vertex] = d_u[vertex];
		dp_v[vertex] = d_v[vertex];
		for(auto& [next_vertex, w] : e[vertex]){
			if(d_s[next_vertex] + w == d_s[vertex]){
				dfs(next_vertex);
				minimize(dp_u[vertex], dp_u[next_vertex]);
				minimize(dp_v[vertex], dp_v[next_vertex]);
			}
		}
		minimize(ans, min(dp_v[vertex] + d_u[vertex], dp_u[vertex] + d_v[vertex]));
	};
	dfs(t);
	cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:19:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |   auto [w, u] = pq.top();
      |        ^
commuter_pass.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |    for(auto& [v, edge_w] : e[u]){
      |              ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   for(auto& [next_vertex, w] : e[vertex]){
      |             ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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