Submission #833522

#	Time	Username	Problem	Language	Result	Execution time	Memory
833522		vjudge1	Exam (eJOI20_exam)	C++17	0 / 100	1066 ms	269488 KiB

exam

#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], dist3[N];
vector<ll> special;
bool ada[N], vis[N];
ll cost;
ll n, m, s, t, u, v, mindist = INF, mindist2 = INF, mindisttotal = INF;
	ll input1, input2, input3;

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){
	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 djikstra3(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++){
		dist3[i] = INF;
	}
	dist3[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(dist3[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);
				dist3[next_node] = next_dist;
				pq.push({next_dist, next_node});
			}
		}
	}
}

void finds(ll cur, ll finish){
	if(cur == finish){
		if(!ada[cur]){
			 //special.push_back(cur);
			 ada[cur] = true;
		}
		return;
	}
	for(auto x : last[cur]){
		if(vis[x]) continue;
		vis[x] = true;
		if(!ada[x]){
			 //special.push_back(x);
			 ada[x] = true;
		}
		finds(x, finish);
	}
	last[cur].clear();
}

void dfs(ll node, ll c){
	if(c == cost && node == t){
		djikstra2(v);
		mindist = INF;
		mindist2 = INF;
		for(auto x : special){
			mindist = min(mindist, dist2[x]);
			// cout << x << " " << dist2[x] << endl;
		}
		djikstra3(u);
		for(auto x : special){
			mindist2 = min(mindist2, dist3[x]);
			// cout << x << " " << dist2[x] << endl;
		}
		mindisttotal = min(mindisttotal, min(mindist+mindist2, dist2[u]));
		return;
	}
	for(auto e : adj[node]){
		if(vis[e.second]) continue;
		vis[e.second] = true;
		special.push_back(e.second);
		dfs(e.second, c+e.first);
		vis[e.second] = false;
		special.pop_back();
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	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});
	}
	for(int i = 0 ; i< N; i++){
		ada[i] = false;
		vis[i] = false;
	}
	if(n <= 300){
		for(int i = 0; i < N; i++){
			last[i].clear();
		}
		djikstra1(s);
		cost = dist1[t];
		vis[s] = true;
		special.push_back(s);
		special.push_back(t);
		dfs(s, 0);
		cout << mindisttotal << endl;
		return 0;
	}
	
	if(s == u){
		djikstra1(s);
		finds(t, s);
		ada[s] = true;
		ada[t] = true;
		// sort(special.begin(), special.end());
		// special.erase(unique(special.begin(), special.end()), special.end());
		djikstra2(v);
		for(int x = 1; x <= n; x++){
			if(ada[x]) mindist = min(mindist, dist2[x]);
			// cout << x << " " << dist2[x] << endl;
		}
		mindist = min(mindist, dist2[u]);
		// for(int i = 1; i <= n; i++){
			// for(auto x : last[i]){
				// cout << i << ":" << x << " ";
			// }
			// cout << endl;
		// }
		cout << mindist;
		return 0;
	}
	else{
		djikstra1(s);
		finds(t, s);
		ada[s] = true;
		ada[t] = true;
		// sort(special.begin(), special.end());
		// special.erase(unique(special.begin(), special.end()), special.end());
		djikstra2(v);
		for(int x = 1; x <= n; x++){
			if(ada[x]) mindist = min(mindist, dist2[x]);
			// cout << x << " " << dist2[x] << endl;
		}
		djikstra3(u);
		for(int x = 1; x <= n; x++){
			if(ada[x]) mindist2 = min(mindist2, dist3[x]);
			// cout << x << " " << dist2[x] << endl;
		}
		mindisttotal = min(mindist+mindist2, dist3[v]);
		cout << mindisttotal;
	}
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22