Submission #1114398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114398		nikolashami	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	622 ms	65548 KiB

commuter_pass

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

#define int int64_t
const int N=1e5+4;
vector<array<int,2>>adj[N];
vector<int>go[N],g[N],rg[N];
int dS[N],dU[N],dV[N],dT[N],dp1[N],dp2[N],ans,n,m,U,V,S,T;

void dijkstra(int p,int d[]){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
	fill(d,d+n+1,1e18);
	d[p]=0;
	pq.push({0,p});
	while(!pq.empty()){
		auto[dd,u]=pq.top();
		pq.pop();
		for(auto&[v,w]:adj[u]){
			if(dd+w<d[v]){
				d[v]=dd+w;
				pq.push({d[v],v});
			}
		}
	}
}

map<array<int,2>,bool>edges;

int vis[N];
void makego(int u){
	vis[u]=1;
	for(auto&[v,w]:adj[u]){
		if(edges[{min(u,v),max(u,v)}])
			continue;
		if(min(dS[u]+dT[v],dS[v]+dT[u])+w==dS[T]){
			go[u].push_back(v);
			go[v].push_back(u);
			edges[{min(u,v),max(u,v)}]=1;
		}
		if(!vis[v])
			makego(v);
	}
}	

void makedir(int u){
	vis[u]=1;
	for(int v:go[u]){
		int node1=u,node2=v;
		if(dS[node1]>dS[node2])
			swap(node1,node2);
		assert(dT[node2]<dT[node1]);
		g[node1].push_back(node2);
		rg[node2].push_back(node1);
		if(!vis[v])
			makedir(v);
	}
}

int f1(int u){
	if(dp1[u]!=-1)
		return dp1[u];
	int ret=dV[u];
	for(auto v:g[u])
		ret=min(ret,f1(v));
	return dp1[u]=ret;
}

int f2(int u){
	if(dp2[u]!=-1)
		return dp2[u];
	int ret=dV[u];
	for(auto v:rg[u])
		ret=min(ret,f2(v));
	return dp2[u]=ret;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>S>>T>>U>>V;

    for(int i=0,u,v,w;i<m;++i){
    	cin>>u>>v>>w;
    	adj[u].push_back({v,w});
    	adj[v].push_back({u,w});
    }

    dijkstra(U,dU);
    dijkstra(V,dV);
    dijkstra(T,dT);
    dijkstra(S,dS);


    makego(S);
    fill(vis,vis+N,0);
    makedir(S);

    fill(dp1,dp1+N,-1);
    fill(dp2,dp2+N,-1);
    ans=dU[V];
    
    for(int i=1;i<=n;++i)
    	if(dS[i]+dT[i]==dT[S])
    		ans=min(ans,dU[i]+min(f1(i),f2(i)));

    cout<<ans;
}

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