제출 #1182869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182869		elotelo966	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	206 ms	29544 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005

const int mod=1000000007;

int n,m,s,t,u,v,cev;

vector<pair<int,int>> adj[lim];

vector<int> ne[lim],ne2[lim];

int vis[lim],dist[lim][4];

int dp[lim][2];

inline void dij(int bas_node,int kim){
	FOR{
		vis[i]=0;
		dist[i][kim]=OYY;
	}
	
	dist[bas_node][kim]=0;
	
	priority_queue<pair<int,int>> pq;
	pq.push({0,bas_node});
	
	while(pq.size()){
		int node=pq.top().se;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		for(auto go:adj[node]){
			if(dist[node][kim]!=OYY && dist[node][kim]+go.se<dist[go.fi][kim]){
				dist[go.fi][kim]=dist[node][kim]+go.se;
				pq.push({-dist[go.fi][kim],go.fi});
			}
		}
	}
}

inline bool check(int node1,int node2,int cost){
	if(dist[node1][0]+dist[node2][3]+cost==dist[t][0])return 1;
	//if(dist[node2][0]+dist[node1][3]+cost==dist[t][0])return 1;
	return  0;
}

inline int dfs(int node,int kim){
	if(~dp[node][kim])return dp[node][kim];
	int cur_cev=dist[node][2];
	if(kim==0){
		for(auto go:ne[node]){
			cur_cev=min(cur_cev,dfs(go,kim));
		}
	}
	else{
		for(auto go:ne2[node]){
			cur_cev=min(cur_cev,dfs(go,kim));
		}
	}
	return dp[node][kim]=cur_cev;
}

inline void cal(){
	FOR{
		vis[i]=0;
	}
	
	queue<int> q;
	
	q.push(s);
	
	while(q.size()){
		int cur_node=q.front();
		q.pop();
		if(vis[cur_node])continue;
		vis[cur_node]=1;
		for(auto go:adj[cur_node]){
			if(vis[go.fi])continue;
			if(check(cur_node,go.fi,go.se)){
				ne[cur_node].pb(go.fi);
				ne2[go.fi].pb(cur_node);
				q.push(go.fi);
			}
		}
	}
}

int32_t main(){
	faster
	cin>>n>>m;
	
	cin>>s>>t>>u>>v;
	
	for(int i=1;i<=m;i++){
		int x,y,z;cin>>x>>y>>z;
		adj[x].pb({y,z});
		adj[y].pb({x,z});
	}
	
	dij(s,0);
	dij(u,1);
	dij(v,2);
	dij(t,3);
	
	cal();
	
	//~ FOR{
		//~ cout<<i<<" "<<ne[i].size()<<'\n';
		
		//~ for(auto a:ne[i])cout<<a<<" ";
		//~ cout<<'\n';
	//~ }
	
	cev=dist[v][1];
	
	memset(dp,-1,sizeof(dp));
	
	dfs(s,0);
	
	dfs(t,1);
	
	FOR{
		if(~dp[i][0] && ~dp[i][1]){
			cev=min(cev,min(dp[i][0],dp[i][1])+dist[i][1]);
		}
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

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