Submission #468656

#	Time	Username	Problem	Language	Result	Execution time	Memory
468656		jamezzz	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	423 ms	26416 KiB

commuter_pass

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define ppb pop_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 100005

int n,m,s,t,u,v,a,b,c,on[maxn];
bool vis[maxn];
ll ans,ds[maxn],dt[maxn],du[maxn],dv[maxn],fu[maxn],fv[maxn];
vii AL[maxn];
vi AL2[maxn];

priority_queue<pll,vector<pll>,greater<pll>> pq;

void dij(int s,ll *dist){
	for(int i=1;i<=n;++i)dist[i]=LINF;
	dist[s]=0;pq.push({0,s});
	while(!pq.empty()){
		ll d;int u;tie(d,u)=pq.top();pq.pop();
		if(d>dist[u])continue;
		for(ii pr:AL[u]){
			if(d+pr.se<dist[pr.fi]){
				dist[pr.fi]=d+pr.se;
				pq.push({dist[pr.fi],pr.fi});
			}
		}
	}
}

void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	fu[u]=du[u];fv[u]=dv[u];
	for(int v:AL2[u]){
		dfs(v);
		mnto(fu[u],fu[v]);
		mnto(fv[u],fv[v]);
	}
	mnto(ans,fu[u]+dv[u]);
	mnto(ans,fv[u]+du[u]);
}

int main(){
	sf("%d%d",&n,&m);
	sf("%d%d",&s,&t);
	sf("%d%d",&u,&v);
	for(int i=0;i<m;++i){
		sf("%d%d%d",&a,&b,&c);
		AL[a].pb(b,c);
		AL[b].pb(a,c);
	}
	dij(s,ds);dij(t,dt);
	dij(u,du);dij(v,dv);
	
	for(int i=1;i<=n;++i){
		for(ii pr:AL[i]){
			if(ds[i]+pr.se+dt[pr.fi]==ds[t]){
				AL2[i].pb(pr.fi);
			}
		}
	}
	
	ans=du[v];
	dfs(s);
	pf("%lld\n",ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:71:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  sf("%d%d",&n,&m);
      |    ^
commuter_pass.cpp:72:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  sf("%d%d",&s,&t);
      |    ^
commuter_pass.cpp:73:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  sf("%d%d",&u,&v);
      |    ^
commuter_pass.cpp:75:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   sf("%d%d%d",&a,&b,&c);
      |     ^

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