Advertisement
hpnq

плохая дейкстра

May 26th, 2024
634
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.80 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. //speed coding handle
  3.  
  4. #define mp make_pair
  5. #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
  6. #define f first
  7. #define s second
  8. #define loop(i, x, n) for (int i = x; i < n; i++)
  9. #define joop(x, n) for (ll j = x; j < n; j++)
  10. #define lp(n) for (ll i = 0; i < n; i++)
  11. #define err cout << "ERROR" << endl;
  12. #define all(x) x.begin(), x.end()
  13. #define pb push_back
  14. #define sz(x) x.size()
  15. #define rndm rng()
  16.  
  17. // types
  18. #define pii pair<int, int>
  19. #define pll pair<ll, ll>
  20. #define vvi vector<vector<int>>
  21. #define vvll vector<vector<ll>>
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. // types of data
  26. #define inf 1000000000
  27. #define infll 1000000000000000000
  28. #define INF ll(1e9)
  29.  
  30. #define md 998244353
  31. #define mod 1000000009
  32. //#define K 239017
  33.  
  34. #define DEBUG 1
  35. using namespace std;
  36. mt19937_64 rng(113113);
  37. uniform_int_distribution<ll> drist;
  38. //const int INF = std::numeric_limits<int>::max();
  39.  
  40. const int MAX_N = 50;
  41.  
  42. int N, m; // количество локаций
  43. float graph[MAX_N][MAX_N]; // матрица смежности
  44. float speed[3]; // скорости роботов
  45.  
  46. void dijkstra(int start, float dist[], float r_speed, int prev[]) {
  47.     bool visited[MAX_N] = {false};
  48. //    loop(i, 0, MAX_N){
  49. //        cout << visited[i] << " ";
  50. //    }
  51.     cout << "\n";
  52.     prev[start] = start;
  53.     for (int i = 0; i < N; ++i) {
  54.         dist[i] = INF;
  55.     }
  56.     dist[start] = 0;
  57.  
  58.     for (int i = 0; i < N; ++i) {
  59.         int u = -1;
  60.         for (int j = 0; j < N; ++j) {
  61.             if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
  62.                 u = j;
  63.             }
  64.         }
  65. //        cout << "u: " << u << endl;
  66.         if (dist[u] == INF) break;
  67.         visited[u] = true;
  68.  
  69.         for (int v = 0; v < N; ++v) {
  70. //            if(v == 2){
  71. //                cout << "u: " << u << " g: " <<  graph[u][v] << endl;
  72. //            }
  73.             if (graph[u][v] && dist[u] + graph[u][v] / r_speed < dist[v]) {
  74.                 dist[v] = dist[u] + graph[u][v]/r_speed;
  75.  
  76. //                cout << "u: " << u << " v: " << v << endl;
  77.                 prev[v] = u;
  78.             }
  79.         }
  80.     }
  81. }
  82. int I[3];
  83. void input(){
  84.     cin >> N >> m;
  85.  
  86.     for(int i = 0; i < N; ++i) {
  87.         for(int j = 0; j < N; ++j) {
  88.             cin >> graph[i][j];
  89.         }
  90.     }
  91.     loop(i, 0, m){
  92.         cin >> I[i];
  93.     }
  94.     loop(i, 0, m){
  95.         cin >> speed[i];
  96.     }
  97.  
  98.  
  99. }
  100.  
  101. void solve(){
  102.     input();
  103.     float mind = -1;
  104.     int prev[3][MAX_N];
  105.     float d[3][MAX_N];
  106.     loop(i, 0, 3){
  107.         loop(j, 0, MAX_N){
  108.             prev[i][j] = 0;
  109.             d[i][j] = inf;
  110.             cout << d[i][j] << " ";
  111.         }
  112.         cout << "\n";
  113.     }
  114.     loop(i, 0, N){
  115.         loop(j, 0, N){
  116.             cout << graph[i][j] << " ";
  117.         }
  118.         cout << "\n";
  119.  
  120.     }
  121. //    cout << "m: " << m << endl;
  122.     loop(i, 0, m){
  123.         dijkstra(I[i], d[i], speed[i], prev[i]);
  124.     }
  125.     cout << "prev: \n";
  126.     loop(i, 0, m){
  127.         loop(j, 0, N){
  128.             cout << prev[i][j] << " ";
  129.         }
  130.         cout << "\n";
  131.     }
  132.     cout << "\ndist: \n";
  133.     loop(i, 0, m){
  134.         loop(j, 0, N){
  135.             cout << d[i][j] << " ";
  136.         }
  137.         cout << "\n";
  138.     }
  139.     loop(p, 0, N) {
  140.         float t[3];
  141.         float middleware = 1;
  142.  
  143.         loop(i, 0, m){
  144.             float dis = d[i][p];
  145.             t[i] = dis;
  146.             middleware = max(middleware, dis);
  147.         }
  148. //        if(t[0] == t[1] or t[0] == t[2] or t[1] == t[2]){
  149. //            mind = min(mind, middleware);
  150. //            err
  151. //            cout << t[0] << " " << t[1] << " " << t[2] << endl;
  152. // // ------------------------------------ ? -------------------------
  153. //        }
  154.         float w = inf;
  155.         loop(i, 0, m){
  156.             loop(j, 0, m){
  157.                 if(i != j){ // перебираю всех разных роботов
  158. //                    cout << p << " " << prev[i][p] << " i: " << i << endl;
  159.                     // проверка если столкнутся на дороге
  160. //                    if(graph[p][prev[i][p]] == 0 or graph[prev[i][p]][p] == 0 or graph[prev[j][p]][p] == 0){
  161. //                        cout << "Never met\n";
  162. //                        cout << graph[p][prev[i][p]] << " " << prev[i][p] ;
  163. //                        return;
  164. //                    }
  165.                     if(d[i][I[j]] == inf){
  166.                         cout << "Never met";
  167.                         return;
  168.                     }
  169.                     if(d[i][prev[i][p]] == d[j][p] and graph[p][prev[i][p]] != 0){
  170.                         // если стояли рядом и их путь одинаковый
  171. //                        err
  172.                         w = min(w, d[j][p] + graph[p][prev[i][p]]/(speed[j] + speed[i]));
  173.                         if(mind == 0){
  174.                             cout << "mind = 0\n";
  175.                             cout << d[j][p] << " " << graph[p][prev[i][p]] << '\n';
  176.                         }
  177.                     }
  178.                     // проверка если столкнутся на пункте
  179.                     if(d[i][prev[i][p]] == d[j][prev[j][p]] and graph[prev[i][p]][p] != 0 and graph[prev[j][p]][p] != 0){
  180.                         cout << "dist len: " << d[i][p] + d[j][p] << endl;
  181.                         w = min(w, d[i][prev[i][p]] + (graph[prev[i][p]][p] + graph[prev[j][p]][p]) / (speed[j] + speed[i]) );
  182.                     }
  183.                 }
  184.                 if(w != inf){
  185.                     mind = max(mind, w);
  186.  
  187.                 }
  188.             }
  189.         }
  190.  
  191.     }
  192.     if(mind == inf){
  193.         cout << "Never meet\n";
  194.         return;
  195.     }
  196.     cout << "Min time for robots:" << mind << endl;
  197. }
  198. int main() {
  199.     freopen("text.txt", "r", stdin);
  200.     solve();
  201.     return 1;
  202. }
  203.  
Advertisement
Comments
Add Comment
Please, Sign In to add comment
Advertisement