제출 #1182866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182866		elotelo966	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	394 ms	24668 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];

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

pair<int,int> dp[lim];

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 pair<int,int> dfs(int node){
	if(vis[node])return dp[node];
	vis[node]=1;
	dp[node]={dist[node][1],dist[node][2]};
	for(auto go:ne[node]){
		pair<int,int> cur=dfs(go);
		cev=min(cev,cur.fi+dist[node][2]);
		cev=min(cev,cur.se+dist[node][1]);
		dp[node].fi=min(dp[node].fi,cur.fi);
		dp[node].se=min(dp[node].se,cur.se);
	}
	//cout<<node<<" "<<dp[node].fi<<" "<<dp[node].se<<endl;
	return dp[node];
}

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);
				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];
	
	FOR{
		vis[i]=0;
	}
	
	dfs(s);

	cout<<cev<<'\n';
	
	return 0;
}

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