Submission #317516

#	Time	Username	Problem	Language	Result	Execution time	Memory
317516		nandonathaniel	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	455 ms	25436 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=100005,INF=1e18;
vector<pii> adj[MAXN];
LL city[4];
LL s,t,u,v,dp[MAXN][2],dist[4][MAXN];

LL DP(LL now,LL stat){
	LL &ret=dp[now][stat];
	if(ret!=-1)return ret;
	ret=dist[3][now];
	for(auto nxt : adj[now]){
		if(stat==0){
			if(dist[0][now]+nxt.second+dist[1][nxt.first]==dist[0][t])ret=min(ret,DP(nxt.first,stat));
		}
		else{
			if(dist[1][now]+nxt.second+dist[0][nxt.first]==dist[1][s])ret=min(ret,DP(nxt.first,stat));
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,m,U,V,w;
	cin >> n >> m >> s >> t >> u >> v;
	for(LL i=1;i<=m;i++){
		cin >> U >> V >> w;
		adj[U].push_back({V,w});
		adj[V].push_back({U,w});
	}
	city[0]=s;city[1]=t;city[2]=u;city[3]=v;
	for(LL i=0;i<4;i++){
		for(LL j=1;j<=n;j++)dist[i][j]=INF;
		dist[i][city[i]]=0;
		priority_queue<pii,vector<pii>,greater<pii> > PQ;
		PQ.push({0,city[i]});
		while(!PQ.empty()){
			pii now=PQ.top();
			PQ.pop();
			if(dist[i][now.second]<now.first)continue;
			for(auto nxt : adj[now.second]){
				if(dist[i][now.second]+nxt.second<dist[i][nxt.first]){
					dist[i][nxt.first]=dist[i][now.second]+nxt.second;
					PQ.push({dist[i][nxt.first],nxt.first});
				}
			}
		}
	}
	memset(dp,-1,sizeof(dp));
	LL ans=dist[2][v];
	for(LL i=1;i<=n;i++){
		if(dist[0][i]+dist[1][i]==dist[0][t])ans=min(ans,dist[2][i]+min(DP(i,0),DP(i,1)));
	}
	cout << ans << '\n';
	return 0;
}

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