Submission #857572

#	Time	Username	Problem	Language	Result	Execution time	Memory
857572		dio_2	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	190 ms	17104 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long)1e18;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	
	vector<vector<pair<int, int>>> adj(n + 1);
	
	while(m--){
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	
	auto Do = [&](int src, vector<long long> &d)->void{
      fill(d.begin(), d.end(), inf);
      vector<bool> in_Q(n + 1);
      d[src] = 0;
      priority_queue<pair<long long, int>> pq;
      pq.push({0, src});
      while(!pq.empty()){
       auto [_, node] = pq.top();		
		 pq.pop();
		 if(in_Q[node]) continue;
		 in_Q[node] = 1;
		 for(auto [to, cost] : adj[node]){
		  if(d[node] + cost < d[to]){
		    d[to] = d[node] + cost;
		    pq.push({-d[to], to});
		  }
		 }
	   }
	};
	
	vector<long long> D1(n + 1);
	Do(s, D1);
	
	int cr = t;
	
	while(cr != s){
		for(auto &[node, cost] : adj[cr]){
			if(D1[node] + cost == D1[cr]){
				cost = 0;
				for(auto &[node2, cost2] : adj[node]){
					if(node2 == cr){
						cost2 = 0;
					}
				}
				cr = node;
				break;
			}
		}
	}
	
	vector<long long> Du(n + 1);
	Do(u, Du);
	
	cout << Du[v] << '\n';
	
	return 0;
}

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