Submission #720005

#	Time	Username	Problem	Language	Result	Execution time	Memory
720005		mariowong	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	742 ms	25784 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

vector <pair<int,long long>  > edge[100005];
long long dis[100005][8];
priority_queue <pair<long long,int>  > pq;
priority_queue <pair<pair<long long,long long>,int>  > pq2;
int a[8];
bool vis[100005];
int main(){
//	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m >> a[1] >> a[2] >> a[3] >> a[4];
	for (int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	for (int i=1;i<=4;i++){
		for (int j=1;j<=n;j++) dis[j][i]=-1;
		pq.push({0,a[i]});
		while (!pq.empty()){
			long long d=-pq.top().first;
			int id=pq.top().second; pq.pop();
			if (dis[id][i] == -1){
				dis[id][i]=d;	
				for (auto j:edge[id]){
					if (dis[j.first][i] == -1) pq.push({-(d+j.second),j.first});	
				}
			}
		}
	}
//	cout << "hi\n";
	long long ans=dis[a[4]][3];
	pq2.push({{0,-1e18},a[1]});
	while (!pq2.empty()){
		long long d=-pq2.top().first.first,mn=-pq2.top().first.second;
		int id=pq2.top().second; pq2.pop();
		if (!vis[id]){
			vis[id]=true;
			mn=min(mn,dis[id][3]);
		//	cout << mn << " " << dis[id][4] << " " << id << "\n";
			if (dis[id][1]+dis[id][2] == dis[a[2]][1]) ans=min(ans,mn+dis[id][4]);
			for (auto j:edge[id]){
				if (!vis[j.first]) pq2.push({{-(d+j.second),-mn},j.first});
			}
		}
	}	
//	cout << ans << "\n";
	for (int i=1;i<=n;i++) vis[i]=false;
	pq2.push({{0,-1e18},a[1]});
	while (!pq2.empty()){
		long long d=-pq2.top().first.first,mn=-pq2.top().first.second;
		int id=pq2.top().second; pq2.pop();
		if (!vis[id]){
			vis[id]=true;
			mn=min(mn,dis[id][4]);
		//	cout << mn << " " << dis[id][4] << " " << id << "\n";
			if (dis[id][1]+dis[id][2] == dis[a[2]][1]) ans=min(ans,mn+dis[id][3]);
			for (auto j:edge[id]){
				if (!vis[j.first]) pq2.push({{-(d+j.second),-mn},j.first});
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

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