fork download 
  1. /*
  2.     Author: Le_bach Ngo Quyen High School
  3. */
  4.  
  5. //#pragma GCC optimize("O3,unroll-loops")
  6. //#pragma GCC optimize("Ofast")
  7. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  8. //#pragma GCC target("avx,avx2,fma")
  9.  
  10. //#define Lebach
  11. #define OFFLINE
  12.  
  13. #include<bits/stdc++.h>
  14. //#include<ext/pb_ds/assoc_container.hpp>
  15. //#include<ext/pb_ds/tree_policy.hpp>
  16.  
  17. using namespace std;
  18. using namespace chrono;
  19. //using namespace __gnu_pbds;
  20.  
  21. #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  22. #define MOD 1000000007
  23. #define MOD1 998244353
  24. #define N 100005
  25. #define FOR(i,a,b) for(int i = a; i <= b; i++)
  26. #define REP(i, b) for(int i = 1; i <= b; i++)
  27. #define FORD(i,a,b) for(int i = a; i >= b; i--)
  28. #define INF 1e18
  29. #define nline "\n"
  30. #define pb push_back
  31. #define ppb pop_back
  32. #define mp make_pair
  33. #define ff first
  34. #define ss second
  35. #define PI 3.141592653589793238462
  36. #define cnt_bits __builtin_popcountll
  37. #define all_subset(mask) (1 << mask)
  38. #define is_bit(pos, mask) ((mask >> pos) & 1)
  39. #define sz(x) ((int)(x).size())
  40. #define all(x) (x).begin(), (x).end()
  41. #define endl '\n'
  42. #define multitest 0
  43.  
  44. #ifdef Lebach
  45. #define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
  46. #else
  47. #define debug(x);
  48. #endif
  49.  
  50. typedef long long ll;
  51. typedef unsigned long long ull;
  52. typedef long double lld;
  53. typedef pair<int, int> pii;
  54.  
  55. /*--------------------------------------------------------------------------------------------------------------------------*/
  56. /// Init
  57.  
  58. int n, m, s, t1, t2, ans, opti_t;
  59. vector<vector<pair<int, int>>> graph(n);
  60. vector<int> d;
  61.  
  62. /*--------------------------------------------------------------------------------------------------------------------------*/
  63.  
  64. void Read(){
  65.     cin >> m >> n >> s >> t1 >> t2;
  66.     graph.resize(n+1);
  67.     d.resize(n+3, INF);
  68.     for(int i = 1; i <= m; i++){
  69.         int u, v, w;
  70.         cin >> u >> v >> w;
  71.         graph[u].push_back({v,w});
  72.         graph[v].push_back({u,w});
  73.     }
  74. }
  75.  
  76. void dis(int node1){
  77.     d[node1] = 0;
  78.  
  79.     priority_queue<pii, vector<pii>, greater<pii>> q;
  80.     q.push({node1, d[node1]});
  81.     while(!q.empty()){
  82.         int v = q.top().ff;
  83.         int d_v = q.top().ss;
  84.         q.pop();
  85.         if(d_v != d[v]) continue;
  86.  
  87.         for(auto edge: graph[v]){
  88.             int v1 = edge.ff;
  89.             int d_v1 = edge.ss;
  90.  
  91.             if(d[v] + d_v1 < d[v1]){
  92.                 d[v1] = d[v] + d_v1;
  93.                 q.push({v1, d[v1]});
  94.             }
  95.         }
  96.     }
  97. }
  98.  
  99. void solve() {
  100.     dis(s);
  101.     if(d[t1] > d[t2]){
  102.         opti_t = t2;
  103.         ans += d[t2];
  104.         d.resize(n+3, INF);
  105.         dis(opti_t);
  106.         ans += d[t1];
  107.     } else {
  108.         opti_t = t1;
  109.         ans += d[t1];
  110.         d.resize(n+3, INF);
  111.         dis(opti_t);
  112.         ans += d[t2];
  113.     }
  114.  
  115.     cout << ans;
  116.  
  117. }
  118.  
  119.  
  120. /*--------------------------------------------------------------------------------------------------------------------------*/
  121.  
  122. void Combination_system(){
  123.     Read();
  124.     solve();
  125.     return;
  126. }
  127.  
  128. int main() {
  129.     #define NAME "TASK"
  130.      if(fopen(NAME".inp", "r")){
  131.          freopen(NAME".inp", "r", stdin);
  132.          freopen(NAME".out", "w", stdout);
  133.      }
  134.  
  135.     fastio();
  136.  
  137.      if(multitest){
  138.          int T; cin >> T;
  139.          while(T--)
  140.              Combination_system();
  141.      } else Combination_system();
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/30SAZD
language:
C++ (gcc 8.3)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!