Submission #832197

#	Time	Username	Problem	Language	Result	Execution time	Memory
832197		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	277 ms	36844 KiB

commuter_pass

#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define rep(i,n,N) for(int i = n; i<=N; ++i)
#define rap(i,n,N) for(int i = n; i>=N; --i)
#define For(i,n,N) for(int i = n; i< N; ++i)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define mems(x,y) memset(x,y,sizeof x)
#define ari(x) array<int,x>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
const int MAX = 2e5 + 5;

int n,m,a,b,c,s,t,U,V,nw;
ll vis[MAX][4],cs,ncs,ans;
pll dp[MAX];
vector<pii> v[MAX];
vector<int> u[MAX];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void gg(int st,int id){
	vis[st][id] = 0;
	pq.push({0, st});
	while(!pq.empty()){
		nw = pq.top().se;
		cs = pq.top().fi;
		pq.pop();
		if(vis[nw][id]!=cs)continue;
		for(auto &i:v[nw]){
			ncs = cs+i.se;
			if(vis[i.fi][id]<=ncs)continue;
			vis[i.fi][id] = ncs;
			pq.push({ncs, i.fi});
		}
	}
	return;
}

void f(int nw){
	pll &ret = dp[nw];
	if(ret.fi!=-1)return;
	ret = {vis[nw][2], vis[nw][3]};
	for(auto i:u[nw]){
		f(i);
		ret.fi = min(ret.fi, dp[i].fi);
		ret.se = min(ret.se, dp[i].se);
	}
	ans = min({ans, ret.fi+vis[nw][3], ret.se+vis[nw][2]});
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m>>s>>t>>U>>V;
	rep(i,1,m){
		cin>>a>>b>>c;
		v[a].pb({b,c});
		v[b].pb({a,c});
	}
	mems(vis, 1);
	gg(s, 0);
	gg(t, 1);
	gg(U, 2);
	gg(V, 3);
	mems(dp, -1);
	rep(i,1,n){
		for(auto j:v[i])if(vis[i][0]+j.se+vis[j.fi][1]==vis[t][0]){
			u[i].pb(j.fi);
		}
	}
	ans = vis[V][2];
	f(s);
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:14:38: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   14 | #define mems(x,y) memset(x,y,sizeof x)
      |                                      ^
commuter_pass.cpp:73:2: note: in expansion of macro 'mems'
   73 |  mems(dp, -1);
      |  ^~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from commuter_pass.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

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