제출 #118013

#제출 시각아이디문제언어결과실행 시간메모리
118013JohnTitorCommuter Pass (JOI18_commuter_pass)C++11
31 / 100
577 ms17772 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Commuter" int n, m; int s, t, u, v; class edge{ public: int a, b, c, x; bool good; void input(){ read(a); read(b); read(c); x=a^b; good=0; } } e[200001]; vector <int> g[100001]; ll f[100001]; class cmp{ public: bool operator ()(pair <int, ll> A, pair <int, ll> B){ return A.second>B.second; } }; priority_queue <pair <int, ll>, vector <pair <int, ll>>, cmp> q; void dij(int a){ FOR(i, 1, n) f[i]=1e18; while(!q.empty()) q.pop(); q.push(mp(a, 0)); f[a]=0; while(!q.empty()){ pair <int, ll> p=q.top(); q.pop(); if(f[p.first]<p.second) continue; for(int i: g[p.first]){ int v=e[i].x^p.first; int cost=e[i].c; if(e[i].good&&(p.first==e[i].a)) cost=0; if(f[v]>p.second+cost){ f[v]=p.second+cost; q.push(mp(v, f[v])); } } } } bool done[100001]; void mark(){ queue <int> q; q.push(t); done[t]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(int i: g[u]){ int v=e[i].x^u; if(f[v]+e[i].c==f[u]){ e[i].good=1; if(e[i].a!=v) swap(e[i].a, e[i].b); if(!done[v]){ done[v]=1; q.push(v); } } } } } int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(m); read(s); read(t); read(u); read(v); FOR(i, 1, m){ e[i].input(); g[e[i].a].pb(i); g[e[i].b].pb(i); } dij(s); mark(); dij(u); ll ans=f[v]; dij(v); ans=min(ans, f[u]); writeln(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...