Submission #649634

#TimeUsernameProblemLanguageResultExecution timeMemory
649634birthdaycakeCommuter Pass (JOI18_commuter_pass)C++17
16 / 100
567 ms25964 KiB
#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif // C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif // - - - - - - // #include<bits/stdc++.h> using namespace std; #define int long long vector<pair<int,int>>adj[200001]; int ans = 1e18; int dij[5][100001]; signed main(){ int n,m; cin >> n >> m; int s,t; cin >> s >> t; int u,v; cin >> u >> v; for(int i = 0; i < m; i++){ int a,b,c; cin >> a >> b >> c; adj[a].push_back({b,c}); adj[b].push_back({a, c}); } set<pair<int,int>>d; for(int i = 1; i <= n; i++){ dij[0][i] = dij[1][i] = dij[2][i] = 1e18; } dij[0][s] = 0; d.insert({dij[0][s], s}); while(d.size()){ auto s = *d.begin(); d.erase(s); if(dij[0][s.second] < s.first) continue; dij[0][s.second] = s.first; for(auto x:adj[s.second]){ if(dij[0][s.second] + x.second < dij[0][x.first]){ dij[0][x.first] = dij[0][s.second] + x.second; d.insert({dij[0][x.first], x.first}); } } } dij[1][t] = 0; d.insert({dij[1][t], t}); while(d.size()){ auto s = *d.begin(); d.erase(s); if(dij[1][s.second] < s.first) continue; dij[1][s.second] = s.first; for(auto x:adj[s.second]){ if(dij[1][s.second] + x.second < dij[1][x.first]){ dij[1][x.first] = dij[1][s.second] + x.second; d.insert({dij[1][x.first], x.first}); } } } dij[2][v] = 0; d.insert({dij[2][v], v}); while(d.size()){ auto s = *d.begin(); d.erase(s); if(dij[2][s.second] < s.first) continue; dij[2][s.second] = s.first; for(auto x:adj[s.second]){ if(dij[2][s.second] + x.second < dij[2][x.first]){ dij[2][x.first] = dij[2][s.second] + x.second; d.insert({dij[2][x.first], x.first}); } } } for(int i = 1; i <= n; i++){ if(dij[0][i] + dij[1][i] == dij[0][t]){ ans = min(ans, dij[2][i]); } } cout << 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...