Submission #833300

#	Time	Username	Problem	Language	Result	Execution time	Memory
833300		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++98	0 / 100	2096 ms	25212 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100005;
const ll INF = 1e15;

vector<pair<ll,ll>> adj[N];
// vector<pair<ll,ll>> adj2[N];
vector<ll> last[N];
ll dist1[N], dist2[N];
set<ll> special;

void djikstra1(ll start){
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
	ll cur_node, cur_dist, next_dist, next_node;
	for(int i = 0; i < N; i++){
		dist1[i] = INF;
	}
	dist1[start] = 0;
	pq.push({0,start});
	while(!pq.empty()){
		cur_node = pq.top().second;
		cur_dist = pq.top().first;
		pq.pop();
		for(auto e : adj[cur_node]){
			next_dist = cur_dist + e.first;
			next_node = e.second;
			if(dist1[next_node] < next_dist) continue;
			else if(dist1[next_node] == next_dist){
				last[next_node].push_back(cur_node);
			}
			else{
				last[next_node].clear();
				last[next_node].push_back(cur_node);
				dist1[next_node] = next_dist;
				pq.push({next_dist, next_node});
			}
		}
	}
}

void djikstra2(ll start){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
	ll cur_node, cur_dist, next_dist, next_node;
	for(int i = 0; i < N; i++){
		dist2[i] = INF;
	}
	dist2[start] = 0;
	pq.push({0,start});
	while(!pq.empty()){
		cur_node = pq.top().second;
		cur_dist = pq.top().first;
		pq.pop();
		for(auto e : adj[cur_node]){
			next_dist = cur_dist + e.first;
			next_node = e.second;
			if(dist2[next_node] < next_dist) continue;
			// else if(dist2[next_node] == next_dist){
				// last[next_node].push_back(cur_node);
			// }
			else{
				// last[next_node].clear();
				// last[next_node].push_back(cur_node);
				dist2[next_node] = next_dist;
				pq.push({next_dist, next_node});
			}
		}
	}
}

void find(ll cur, ll finish){
	if(cur == finish){
		special.insert(cur);
		return;
	}
	for(auto x : last[cur]){
		special.insert(x);
		find(x, finish);
	}
}
int main(){
	ll n, m, s, t, u, v, mindist = INF;
	ll input1, input2, input3;
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 0; i < m; i++){
		cin >> input1 >> input2 >> input3;
		adj[input1].push_back({input3, input2});
		adj[input2].push_back({input3, input1});
		// adj2[input2].push_back({input3, input1});
	}
	djikstra1(s);
	find(t, s);
	djikstra2(v);
	for(auto x : special){
		mindist = min(mindist, dist2[x]);
		// cout << x << " " << dist2[x] << endl;
	}
	// for(int i = 1; i <= n; i++){
		// for(auto x : last[i]){
			// cout << i << ":" << x << " ";
		// }
		// cout << endl;
	// }
	cout << mindist;
}

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