Submission #1271113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271113		nthvn	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	970 ms	78508 KiB

commuter_pass

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

#define int long long
#define fi first
#define se second
#define pii pair<int,int> 
#define pll pair<long long,long long>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
#define mp make_pair
const ll inf = 1e17;
const int N = 2e5+5;
int n,m;
int A,B,C,D;
vector<pii> g[N];

void predij(int st, ll d[]){
	for(int i=1;i<=n;i++) d[i]= inf;
	
	priority_queue<pll, vector<pll>, greater<pll>>pq;
	pq.push({d[st]=0, st});
	while(!pq.empty()){
		ll du = pq.top().fi, u= pq.top().se;
		pq.pop();
		if(du!=d[u]) continue;
		for(auto &x: g[u]){
			int v= x.fi, uv= x.se;
			if(d[v]> d[u]+uv) {
				pq.push({d[v]= du+uv, v});
			}
		}
	}
}
ll dc[N], dd[N];

pll d[N][5];
struct Node{
	ll du, u, t, c;
	bool operator <(const Node &o)const{
		if(du==o.du){
			return c> o.c;
		}
		return du > o.du;
	}
};

void dij(){
	priority_queue<Node> pq;
	d[A][0] = {0,0};
	d[A][1] = {0,dc[A]};
	d[A][2] = {0,dc[A]+ dd[A]};
	
	pq.push({0,A,0,0});
	pq.push({0,A,1,dc[A]});
	pq.push({0,A,2,dc[A]+dd[A]});
	
	while(!pq.empty()){
		Node top = pq.top();
		pq.pop();
		ll du = top.du, u= top.u, t= top.t, c= top.c;
		if(mp(du,c)!=d[u][t]) continue;
		for(auto &x: g[u]){
			int v= x.fi, uv = x.se;
			if(t==0){
				if(d[v][0]> mp(du+uv, c)){
					d[v][0] = mp(du+uv,c);
					pq.push({du+uv, v, 0, c});
				}
				if(d[v][1]> mp(du+uv, c+ dc[v])){
					d[v][1] = mp(du+uv, c+dc[v]);
					pq.push({du+uv, v, 1, c+ dc[v]});
				}
				if(d[v][2]>mp(du+uv, c+dc[v]+dd[v])){
					d[v][2] = mp(du+uv, c+dc[v]+dd[v]);
					pq.push({du+uv, v, 2, c+ dc[v]+dd[v]});
				}
			}
			else if(t==1){
				if(d[v][1]> mp(du+uv, c)){
					d[v][1] = mp(du+uv,c);
					pq.push({du+uv, v, 1, c});
				}
				if(d[v][2]> mp(du+uv, c+ dd[v])){
					d[v][2] = mp(du+uv, c+dd[v]);
					pq.push({du+uv, v, 2, c+ dd[v]});
				}
			}
			else{
				if(d[v][2]> mp(du+uv, c)){
					d[v][2] = mp(du+uv,c);
					pq.push({du+uv, v, 2, c});
				}
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("tunnel.INP", "r")){
		freopen("tunnel.INP", "r", stdin);
		freopen("tunnel.OUT", "w", stdout);
	}
	cin>>n>>m;
	cin>>A>>B>>C>>D;
	for(int i=1;i<=m;i++){
		int u,v,w; cin>>u>>v>>w;
		g[u].pb({v,w});
		g[v].pb({u,w});
	}
	
	fill_n(&d[0][0], sizeof(d)/sizeof(d[0][0]), mp(inf,inf));
	predij(C,dc);
	predij(D,dd);
	dij();
	ll res1 =d[B][2].se;
	
	fill_n(&d[0][0], sizeof(d)/sizeof(d[0][0]), mp(inf,inf));
	predij(D,dc);
	predij(C,dd);
	dij();
	ll res2 = d[B][2].se;
	
	cout<<min({res1,res2, dc[C]});
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:105:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 freopen("tunnel.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:106:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |                 freopen("tunnel.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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