Submission #761500

#TimeUsernameProblemLanguageResultExecution timeMemory
761500bLICCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
315 ms20964 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define uniq(v) v.erase(unique(all(v)), v.end()) #define ft first #define sd second #define pb push_back #define eb emplace_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;} ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);} template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } // use ?: with brackets (?:) // check for overflow // think about dp // Read the statement carefully const int maxN = 1e5+5; const int maxK = 8001; vll adj[maxN]; int n, m; vl dijkstra(int s){ vl dist(n+1, INFLL); dist[s] = 0; priority_queue<pll, vll, greater<pll>> pq; pq.emplace(0, s); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if (d!=dist[u]) continue; for (auto& [v, w]:adj[u]){ if (dist[v]>dist[u] + w){ dist[v] = dist[u] + w; pq.emplace(dist[v], v); } } } return dist; } ll ans; vl ds, du, dv; void dijkstra1(int start, int end) { vl dist(n+1, INFLL); dist[start] = 0; priority_queue<pll, vll, greater<pll>> pq; pq.emplace(0, start); vl dpu(n+1, INFLL); vl dpv(n+1, INFLL); dpu[start] = du[start]; dpv[start] = dv[start]; while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if (d!=dist[u]) continue; for (auto& [v, w]:adj[u]){ if (dist[v]>dist[u] + w){ dist[v] = dist[u] + w; pq.emplace(dist[v], v); dpu[v] = min(dpu[u], du[v]); dpv[v] = min(dpv[u], dv[v]); } else if (dist[v] == dist[u] + w){ if (min(dpu[u], du[v]) + min(dpv[u], dv[v]) <= dpu[v] + dpv[v]){ dpu[v] = min(dpu[u], du[v]); dpv[v] = min(dpv[u], dv[v]); } } } } ans = min(ans, dpu[end]+dpv[end]); } void solve(){ int s, t, u, v; cin>>n>>m; cin>>s>>t>>u>>v; for (int i = 0;i<m;i++){ int u, v, w;cin>>u>>v>>w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } ds = dijkstra(s); du = dijkstra(u); dv = dijkstra(v); ans = du[v]; dijkstra1(s, t); dijkstra1(t, s); cout<<ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define ONLINE_JUDGE #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); freopen("debug.dbg", "w", stderr); int tt = clock(); #endif int t=1, i = 1; // cin>>t; while(t--){ // cout<<"Case #"<<i++<<": "; solve(); cout<<'\n'; } #ifndef ONLINE_JUDGE cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl; tt = clock(); #endif }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:187:14: warning: unused variable 'i' [-Wunused-variable]
  187 |     int t=1, i = 1;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...