Submission #241226

#	Time	Username	Problem	Language	Result	Execution time	Memory
241226		dsjong	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	464 ms	32360 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[5][100005];
bool vis[100005];
vector<pair<ll, ll>>adj[100005];
vector<ll>adj2[100005];
class cmp{
public:
	bool operator()(pair<ll, ll>p1, pair<ll, ll>p2){
		return p1.second>p2.second;
	}
};
void dijkstra(int src, int idx){
	for(int i=0;i<100005;i++) dis[idx][i]=1e16;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, cmp>pq;
	dis[idx][src]=0;
	pq.push({src, 0});
	memset(vis, 0, sizeof vis);
	while(!pq.empty()){
		ll x=pq.top().first, w=pq.top().second;
		pq.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(auto u:adj[x]){
			ll y=u.first, cw=u.second;
			if(dis[idx][y]>cw+w){
				dis[idx][y]=cw+w;
				pq.push({y, dis[idx][y]});
			}
		}
	}
}
vector<int>tour;
void dfs(int x){
	vis[x]=true;
	for(int y:adj2[x]){
		if(vis[y]) continue;
		dfs(y);
	}
	tour.push_back(x);
}
ll mini[100005];
ll solve(int a, int b){
	ll ans=LONG_LONG_MAX;
	for(int i:tour){
		mini[i]=dis[b][i];
		for(int j:adj2[i]){
			mini[i]=min(mini[i], mini[j]);
		}
		ans=min(ans, dis[a][i]+mini[i]);
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, s, t, u, v;
	cin>>n>>m>>s>>t>>u>>v;
	vector<pair<pair<ll, ll>, ll>>edges;
	for(int i=1;i<=m;i++){
		ll x, y, w;
		cin>>x>>y>>w;
		edges.push_back({{x, y}, w});
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}
	dijkstra(s, 1);
	dijkstra(t, 2);
	dijkstra(u, 3);
	dijkstra(v, 4);
	/*for(int i=1;i<=4;i++){
		for(int j=1;j<=n;j++){
			cout<<dis[i][j]<<" ";
		}
		cout<<endl;
	}*/
	for(auto i:edges){
		ll x=i.first.first, y=i.first.second, w=i.second;
		if(dis[1][x]+dis[2][y]+w==dis[1][t]) adj2[x].push_back(y);
		else if(dis[1][y]+dis[2][x]+w==dis[1][t]) adj2[y].push_back(x);
	}
	memset(vis, false, sizeof vis);
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs(i);
	}
	ll ans=dis[3][v];
	ans=min(ans, solve(3, 4));
	ans=min(ans, solve(4, 3));
	cout<<ans;
}

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