제출 #669358

#제출 시각아이디문제언어결과실행 시간메모리
669358beedleCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
2085 ms16888 KiB
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <set> #include <iterator> #include <stack> #include <map> #include <math.h> #include <bitset> #include <deque> #include <string> #include <tuple> #include <queue> #include <numeric> #include <complex> #include <assert.h> #include <unordered_set> #include <unordered_map> #define ll long long #define ld long long double #define rep(i, a, b) for (long long i = a; i <= b; i++) #define mod 1000000007ll #define INF 1e18 #define pb push_back #define ff first #define ss second #define endl '\n' #define all(x) (x).begin (), (x).end () #define sz(x) (ll) (x).size () #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin()) #define rank rnk #define log lg #define fast \ ios_base::sync_with_stdio (false); \ cin.tie (NULL); \ cout.tie (NULL) using namespace std; vector <pair<ll,ll>> adj[100000+1]; vector <ll> du(1e5+1,INF), dv(1e5+1,INF); void getdist(ll source, vector <ll> &d) { set<pair<ll,ll>> s; s.insert({0,source}); d[source]=0; while(!s.empty()) { auto v=*s.rbegin(); s.erase(v); for(auto u:adj[v.ss]) if(d[u.ff]>v.ff+u.ss) { s.erase({d[u.ff],u.ff}); d[u.ff]=v.ff+u.ss; s.insert({d[u.ff],u.ff}); } } } signed main() { fast; // freopen("curling.in","r",stdin); // freopen("curling.out","w",stdout); ll n,m; cin>>n>>m; ll s,t,u,v; cin>>s>>t>>u>>v; rep(i,1,m) { ll a,b,c; cin>>a>>b>>c; adj[a].pb({b,c}); adj[b].pb({a,c}); } getdist(u,du); getdist(v,dv); // set <pair<ll,ll>> st; // vector <ll> d(n+1,INF); // vector <ll> mindu(n+1); // vector <ll> myscoreu(n+1); // vector <ll> bestscoreu(n+1); // vector <ll> mindv(n+1), myscorev(n+1), bestscorev(n+1); // d[s]=0; // mindu[s]=du[s]; // mindv[s]=dv[s]; // myscoreu[s]=myscorev[s]=bestscoreu[s]=bestscorev[s]=d[u]+dv[s]; // st.insert({0,s}); // while(!st.empty()) // { // auto [dist, vertex]=*st.rbegin(); // st.erase({dist,vertex}); // for(auto u:adj[vertex]) // { // if(d[u.ff]>dist+u.ss) // { // st.erase({d[u.ff],u.ff}); // d[u.ff]=dist+u.ss; // st.insert({d[u.ff],u.ff}); // mindu[u.ff]=min(du[u.ff],mindu[vertex]); // myscoreu[u.ff]=dv[u.ff]+mindu[u.ff]; // bestscoreu[u.ff]=min(myscoreu[u.ff],bestscoreu[vertex]); // mindv[u.ff]=min(dv[u.ff],mindv[vertex]); // myscorev[u.ff]=du[u.ff]+mindv[u.ff]; // bestscorev[u.ff]=min(myscorev[u.ff],bestscorev[vertex]); // } // else if(d[u.ff]==dist+u.ss) // { // st.insert({d[u.ff],u.ff}); // mindu[u.ff]=min({mindu[u.ff],mindu[vertex],du[u.ff]}); // myscoreu[u.ff]=min(myscoreu[u.ff], dv[u.ff]+mindu[u.ff]); // bestscoreu[u.ff]=min({myscoreu[u.ff], bestscoreu[vertex], bestscoreu[u.ff]}); // mindv[u.ff]=min({mindv[u.ff],mindv[vertex],dv[u.ff]}); // myscorev[u.ff]=min(myscorev[u.ff], du[u.ff]+mindv[u.ff]); // bestscorev[u.ff]=min({myscorev[u.ff], bestscorev[vertex], bestscorev[u.ff]}); // } // } // } // cout<<min(bestscoreu[t], bestscorev[t])<<endl; cout<<1<<endl; return 0; } /* 6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1 8 8 5 7 6 8 1 2 2 2 3 3 3 4 4 1 4 1 1 5 5 2 6 6 3 7 7 4 8 8 5 5 1 5 2 3 1 2 1 2 3 10 2 4 10 3 5 10 4 5 10 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...