Submission #1196761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196761		korticz	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	412 ms	20992 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ve,ed,s,t,u,v,a,b,c;
vector<vector<pair<int,int>>> adj;
vector<int> distS,distT,dist;

void dijkstra (int st,vector<int>& dist) {
	dist[st]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,st});
	while(!pq.empty()) {
		auto[w,now]=pq.top();
		pq.pop();
		for (auto&[tow,to]:adj[now]) {
			if (dist[to]>tow+w) {
				dist[to]=tow+w;
				pq.push({tow+w,to});
			}
		}
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>ve>>ed>>s>>t>>u>>v;
	adj.resize(ve+1);
	distS.assign(ve+1,LLONG_MAX);
	distT.assign(ve+1,LLONG_MAX);
	dist.assign(ve+1,LLONG_MAX);
	for (int i=0;i<ed;i++) {
		cin>>a>>b>>c;
		adj[a].push_back({c,b});
		adj[b].push_back({c,a});
	}
	dijkstra(s,distS);
	dijkstra(t,distT);
	set<int> compass;
	for (int i=1;i<=ve;i++) {
		if (distS[i]+distT[i]==distS[t]) {
			compass.insert(i);
		}
	}
	dist[u]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,u});
	while(!pq.empty()) {
		auto[w,now]=pq.top();
		pq.pop();
		for (auto&[tow,to]:adj[now]) {
			if (compass.count(now)&&compass.count(to)) tow=0;
			if (dist[to]>tow+w) {
				dist[to]=tow+w;
				pq.push({tow+w,to});
			}
		}
	}
	cout<<dist[v];
	return 0;
}

/*
7 8 
4 6 
1 7
1 2 1
1 3 9
3 4 9
4 5 1
4 2 2
2 6 2
5 6 3
6 7 5
*/

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