이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/***************************************************************
* 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;
}
컴파일 시 표준 에러 (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) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |