Submission #881371

#	Time	Username	Problem	Language	Result	Execution time	Memory
881371		billyisme	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	297 ms	36968 KiB

commuter_pass

/***************************************************************
*             Author : Nguyen Trong Van Viet                   *
*                        Age : 17                              *
*      School : 12T2 Le Khiet High School for the Gifted       *
*            Hometown :  Quang Ngai , Viet Nam .               *
* Khanh An is my lover :) the more I code  , the nearer I am   *
****************************************************************/
#define TASK "text"
#define INPUT TASK".INP" 
#define OUTPUT TASK".OUT"

bool mtt = 0 ;
int test = 1 ;  

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

#define             ll  long long 
#define             db  double 
#define             ve  vector 
#define             vi  vector<int>
#define            vll  vector<ll>
#define            str  string
#define             pb  push_back
#define             pk  pop_back
#define             el  '\n'
#define            pii  pair<int,int>
#define            pll  pair<ll,ll>
#define             mp  make_pair 
#define             fi  first 
#define             se  second
#define         uni(a)  sort(all(a)),a.resize(unique(all(a))-a.begin()) 
#define     FOR(i,a,b)  for(int i=(int)(a);i<=(int)(b);i++)
#define    FORD(i,a,b)  for(int i=(int)(a);i>=(int)(b);i--)
#define    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
#define         all(a)  a.begin(),a.end()  
#define             LB  lower_bound
#define             UB  upper_bound 
#define            tct  template<class T>
#define     BIT(msk,i)  (msk>>(i)&1)
#define        M(i)  (1ll<<(i))
#define          SZ(_)  (int)(_.size())
#define           btpc  __builtin_popcountll
#define            ctz  __builtin_ctzll 
ll lg(ll a){return __lg(a);}
ll sq(ll a){return a*a;}  
ll gcd(ll a,ll b){return __gcd(a,b);} 
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll rd(ll l , ll r ){return l+1LL*rand()*rand()%(r-l+1);}
#define prt(a,n) FOR(_i,1,n)cout<<a[_i]<<" ";cout<<el;
#define prv(a) for(auto _v:a)cout<<_v<<" "; cout<<el; 

tct bool mini(T& a,T b){return (a>b)?a=b,1:0;}
tct bool maxi(T& a,T b){return (a<b)?a=b,1:0;}

int xx[] = {0,-1,0,1} ; 
int yy[] = {-1,0,1,0} ;

const db PI = acos(-1) , EPS = 1e-9;
const ll inf = 1e18 , cs = 331 , sm = 1e9+7; 
const int N = 2e5+5 , oo = 2e9 , LO = 17 , CH = 26 ; 


int n , m ;
struct ke
{
	int v  ,w ; 
}; 
ve<ke>g[N] ; 
int S ,T , U ,V  ; 
struct Edge{
	int u ,v ,w ; 
}E[N] ; 

void doc()
{
    cin>> n >> m; 
    cin>>S>>T ; 
    cin>>U>>V ;
    FOR(i,1,m)
    {
    	int u,v  ,c; cin>> u >>v>>c ;
    	g[u].pb({v,c}) ; 
    	g[v].pb({u,c}) ;
    	E[i] = {u,v,c}; 
    }
}

namespace sub1
{
	struct DL
	{
		int u ; 
		ll val; 
	} ; 
	struct cmp
	{
		bool operator()(const DL&a , const DL&b)const
		{
			return a.val>b.val; 
		}
	} ; 
	void dij(int S , ll f[])
	{
		priority_queue<DL,ve<DL>,cmp>q ;

		FOR(i,1,n)f[i] = inf ;
		f[S]= 0 ; 
		q.push({S,0}) ;
		while(!q.empty())
		{
			int u = q.top().u; 
			ll val = q.top().val;
			q.pop() ;
			if(f[u]<val)continue ;
			for(auto x:g[u])
			{
				int v=x.v ;
				int w=x.w; 
				if(mini(f[v],f[u]+w))q.push({v,f[v]}) ; 
			}
		}
	}
	ll fs[N] , ft[N] , fu[N] , fv[N] ; 
	vi adj[N] ; 
	void build()
	{
		FOR(i,1,m)
		{
			int u =E[i].u ; 
			int v =E[i].v ;
			int w = E[i].w ; 
			if(fs[u]+ft[v]+w==fs[T])adj[u].pb(v) ; 
			else if(fs[v]+ft[u]+w==fs[T])adj[v].pb(u) ; 
		}
	}	
	ll MU[N] , MV[N] ; 
	ll res  =inf;  
	void dfs(int u )
	{
		if(MU[u]!=inf)return ; 
		MU[u] = fu[u] ; 
		MV[u] = fv[u] ; 
		// cout<<u<<" "<<MV[u]<<el;
		for(auto v:adj[u])
		{
			dfs(v) ; 
			mini(MU[u],MU[v]) ; 
			mini(MV[u],MV[v]) ; 
		}
		mini(res,fu[u]+MV[u]) ; 
		mini(res,fv[u]+MU[u]) ; 

	}
    void xuly()
    {
    	dij(S,fs) ;
    	dij(T,ft) ; 
    	dij(U,fu) ;
    	dij(V,fv) ; 
    	build() ;
    	FOR(i,1,n)MU[i] = MV[i] = inf;
    	res = fu[V] ; 
    	dfs(S) ;
    	// cout<<fu[1]<<" "<<MV[1]<<el;
    	cout<<res; 
    }
}

/*  DON'T BELIEVE LOVE WILL INSPIRE YOU ->  TRAIN HARDER ->  YOU WILL GET THE LOVE YOU WANT !!*/

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
    if(fopen(INPUT,"r"))
    {
        freopen(INPUT ,"r",stdin) ;
        freopen(OUTPUT,"w",stdout);
    }
    else if(fopen("text.INP","r"))
    {
        freopen("text.INP","r",stdin) ; 
        freopen("text.OUT","w",stdout) ;   
    }
    if(mtt)cin>>  test;
    FOR(i,1,test)
    {
        doc() ; 
        sub1::xuly() ; 
    }
    cerr<<el<<"Love KA very much !!! " << clock() <<"ms"<<el;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(INPUT ,"r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen(OUTPUT,"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("text.INP","r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen("text.OUT","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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