Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Apr 10th, 2020 281 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <stdio.h>
  5. //#include <algorithm>
  6. #define maxN 100001
  7. #define Infi 200000001
  8. using namespace std;
  9.  
  10. // A-ból B-be vezető legrövidebb út kiszámítása Dijkstra algoritmussal
  11.  
  12. // TODO: megérteni, átírni az én nyelvemre max nélkül vectorokkal, implementálni a legnagyobb lehetséges teherbírás koncepcióját!!!
  13. // Note: él structhoz hozzáadni elemként, (minden út teherbírása az összes él teherbírása közötti minimum) -> ezt minden útra eltárolni,
  14. // valamint a súlyegyenlőség esetén nagyobb teherbírású utat választani; nehéz rész: eltárolni a teljes út teherbírását és azt
  15. // összehasonlítani, nem csak a jelenlegi élét, valamint a teljes elmentett út cseréje.
  16.  
  17. struct El
  18. {
  19.     int pont, suly;
  20.     El(int u, int s)
  21.     {
  22.         pont = u; suly = s;
  23.     };
  24.     bool operator<(const El& jobb) const
  25.     {
  26.         return suly > jobb.suly || (suly == jobb.suly && pont > jobb.pont);
  27.     }
  28. };
  29.  
  30. vector<El> G[maxN];
  31. priority_queue<El> S;
  32. int n, A, B;
  33.  
  34. int Apa[maxN];
  35. int Tav[maxN];
  36. bool Kesz[maxN];
  37.  
  38. void Dijkstra(int r)
  39. {
  40.     //Globális: G,Kesz,Tav,Apa
  41.     int ujtav;
  42.     El e = El(0, 0); El u = El(0, 0);
  43.     for (int v = 1; v <= n; ++v)
  44.     {//inicializálás
  45.         Kesz[v] = false; Tav[v] = Infi;
  46.     }
  47.     Tav[r] = 0; Apa[r] = 0;
  48.     S.push(El(r, Tav[r]));
  49.     while (S.size() > 0)
  50.     {
  51.         u = S.top(); S.pop();
  52.         if (Kesz[u.pont]) continue;
  53.         Kesz[u.pont] = true;
  54.         for (El uv : G[u.pont])
  55.         {
  56.             ujtav = Tav[u.pont] + uv.suly;
  57.             if (!Kesz[uv.pont] && ujtav < Tav[uv.pont])
  58.             {
  59.                 e.pont = uv.pont; e.suly = ujtav;
  60.                 S.push(e);
  61.                 Tav[uv.pont] = ujtav;
  62.                 Apa[uv.pont] = u.pont;
  63.             }
  64.         }
  65.     }
  66. }
  67.  
  68. void Beolvas()
  69. {
  70.     int m, u, v, s;
  71.     cin >> n >> m;
  72.     cin >> A >> B;
  73.     for (int i = 0; i < m; i++)
  74.     {
  75.         cin >> u >> v >> s;
  76.         G[u].push_back(El(v, s));
  77.         G[v].push_back(El(u, s));
  78.     }
  79. }
  80.  
  81. int main()
  82. {
  83.     Beolvas();
  84.     Dijkstra(A);
  85.     vector<int> Ut;
  86.     int x = B;
  87.     while (x != A)
  88.     {
  89.         Ut.push_back(x);
  90.         x = Apa[x];
  91.     }
  92.     cout << Tav[B] << endl;
  93.     cout << A;
  94.     for (int i = Ut.size() - 1; i >= 0; i--)
  95.         cout << " " << Ut[i];
  96.     cout << endl;
  97. }
  98.  
  99. /*
  100. 6 9
  101. 1 6
  102. 1 2 3
  103. 1 4 7
  104. 1 5 6
  105. 2 3 4
  106. 2 5 3
  107. 4 5 8
  108. 3 5 5
  109. 3 6 2
  110. 5 6 3
  111.  
  112. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top