7oSkaaa

C

Jun 30th, 2022 (edited)
666
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define cin_2d(vec, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m && cin >> vec[i][j]; j++);
  6. #define cout_2d(vec, n, m) for(int i = 0; i < n; i++, cout << "\n") for(int j = 0; j < m && cout << vec[i][j] << " "; j++);
  7. #define cout_map(mp) for(auto& [f, s] : mp) cout << f << "  " << s << "\n";
  8. #define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
  9. #define fixed(n) fixed << setprecision(n)
  10. #define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  11. #define fill(vec, value) memset(vec, value, sizeof(vec));
  12. #define Num_of_Digits(n) ((int)log10(n) + 1)
  13. #define mod_combine(a, b, m) (((a % m) * (b % m)) % m)
  14. #define all(vec) vec.begin(), vec.end()
  15. #define rall(vec) vec.rbegin(), vec.rend()
  16. #define sz(x) int(x.size())
  17. #define debug(x) cout << #x << ": " << (x) << "\n";
  18. #define fi first
  19. #define se second
  20. #define ll long long
  21. #define ull unsigned long long
  22. #define Mod  1'000'000'007
  23. #define OO 2'000'000'000
  24. #define EPS 1e-9
  25. #define PI acos(-1)
  26. template < typename T = int > using Pair = pair < T, T >;
  27.  
  28. template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
  29.     for (auto &x: v) in >> x;
  30.     return in;
  31. }
  32.  
  33. template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
  34.     for (const T &x: v) out << x << ' ';
  35.     return out;
  36. }
  37.  
  38. void AhMeD_HoSSaM(){
  39.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  40.     // #ifndef ONLINE_JUDGE
  41.     //     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  42.     // #endif
  43. }
  44.  
  45. struct Edge {
  46.    
  47.     ll v, w;
  48.    
  49.     Edge(int V = 0, int W = 0): v(V), w(W) {}
  50.    
  51.     bool operator < (const Edge& e) const {
  52.         return w > e.w;
  53.     }
  54. };
  55.  
  56. vector < vector < Edge > > adj, rev_adj;
  57. int n, m;
  58.  
  59. vector < ll > Dijkstra(ll src, vector < vector < Edge > >& G){
  60.     vector < ll > dist(sz(G), LLONG_MAX);
  61.     dist[src] = 0;
  62.     priority_queue < Edge > pq;
  63.     pq.push(Edge(src, 0));
  64.     while(!pq.empty()){
  65.         auto [u, cost] = pq.top();
  66.         pq.pop();
  67.         if(dist[u] < cost) continue;
  68.         for(auto& [v, w] : G[u]){
  69.             if(dist[v] > dist[u] + w){
  70.                 dist[v] = dist[u] + w;
  71.                 pq.push(Edge(v, dist[v]));
  72.             }
  73.         }
  74.     }
  75.     return dist;
  76. }
  77.  
  78. ll try_node(ll dest, ll src1, ll src2){
  79.     vector < ll > dist1 = Dijkstra(src1, adj);
  80.     vector < ll > dist2 = Dijkstra(src2, adj);
  81.     vector < ll > dist_d = Dijkstra(dest, rev_adj);
  82.     ll ans = LLONG_MAX;
  83.     for(int i = 1; i <= n; i++){
  84.         if(dist1[i] == LLONG_MAX || dist2[i] == LLONG_MAX || dist_d[i] == LLONG_MAX) continue;
  85.         ans = min(ans, dist1[i] + dist2[i] + dist_d[i]);
  86.     }
  87.     return (ans == LLONG_MAX ? LLONG_MAX : ans);
  88. }
  89.  
  90. void Solve(){
  91.     cin >> n >> m;
  92.     adj = vector < vector < Edge > > (n + 10);
  93.     rev_adj = vector < vector < Edge > > (n + 10);
  94.     for(int i = 0, u, v, w; i < m && cin >> u >> v >> w; i++)
  95.         adj[u].push_back(Edge(v, w)), rev_adj[v].push_back(Edge(u, w));
  96.     ll x, y, z;
  97.     cin >> x >> y >> z;
  98.     vector < Pair < ll > > ans = {{try_node(x, y, z), x}, {try_node(y, x, z), y}, {try_node(z, x, y), z}};
  99.     sort(all(ans), [&](const Pair < ll > &a, const Pair < ll > &b){
  100.         return a.fi < b.fi || (a.fi == b.fi && a.se < b.se);
  101.     });
  102.     if(ans[0].fi >= OO) return cout << -1 << '\n', void();
  103.     cout << ans[0].se << ' ' << ans[0].fi << '\n';
  104. }
  105.  
  106. int main(){
  107.     AhMeD_HoSSaM();
  108.     int t = 1;
  109.     //cin >> t;
  110.     while(t--)
  111.         Solve();
  112.     return 0;
  113. }
RAW Paste Data Copied