fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Używamy long long dla bezpieczeństwa przy sumowaniu czasów przejazdu
  8. const long long INF = 1e18;
  9.  
  10. struct Punkt {
  11.     long long x, y;
  12. };
  13.  
  14. struct Ulica {
  15.     int od, cel; // Zmieniono 'do' na 'cel'
  16.     long long t;
  17.     long long dx, dy;
  18. };
  19.  
  20. // Macierz odległości umieszczona globalnie
  21. long long dist[505][505];
  22.  
  23. int main() {
  24.     ios_base::sync_with_stdio(false);
  25.     cin.tie(NULL);
  26.  
  27.     int n, m, p;
  28.     if (!(cin >> n >> m >> p)) return 0;
  29.  
  30.     vector<Punkt> punkty(n + 1);
  31.     for (int i = 1; i <= n; ++i) {
  32.         cin >> punkty[i].x >> punkty[i].y;
  33.     }
  34.  
  35.     vector<Ulica> ulice(m + 1);
  36.     for (int i = 1; i <= m; ++i) {
  37.         // Zmieniono 'do' na 'cel' w cin i obliczeniach
  38.         cin >> ulice[i].od >> ulice[i].cel >> ulice[i].t;
  39.         ulice[i].dx = punkty[ulice[i].cel].x - punkty[ulice[i].od].x;
  40.         ulice[i].dy = punkty[ulice[i].cel].y - punkty[ulice[i].od].y;
  41.     }
  42.  
  43.     vector<int> przystanki(p);
  44.     for (int i = 0; i < p; ++i) {
  45.         cin >> przystanki[i];
  46.     }
  47.  
  48.     for (int i = 1; i <= m; ++i) {
  49.         for (int j = 1; j <= m; ++j) {
  50.             dist[i][j] = (i == j) ? 0 : INF; 
  51.             // Inicjalizacja: 0 jeśli ta sama ulica, INF w innych przypadkach
  52.         }
  53.     }
  54.  
  55.     // Budowanie grafu ulic
  56.     for (int i = 1; i <= m; ++i) {
  57.         for (int j = 1; j <= m; ++j) {
  58.             // Sprawdzamy połączenie: koniec ulicy i musi być początkiem ulicy j
  59.             if (ulice[i].cel == ulice[j].od) {
  60.                 // Iloczyn skalarny dla kąta <= 90 stopni
  61.                 if (ulice[i].dx * ulice[j].dx + ulice[i].dy * ulice[j].dy >= 0) {
  62.                     dist[i][j] = ulice[i].t + ulice[j].t;
  63.                 }
  64.             }
  65.         }
  66.     }
  67.  
  68.     // Floyd-Warshall
  69.     for (int k = 1; k <= m; ++k) {
  70.         for (int i = 1; i <= m; ++i) {
  71.             if (dist[i][k] == INF) continue;
  72.             for (int j = 1; j <= m; ++j) {
  73.                 if (dist[k][j] < INF) {
  74.                     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  75.                 }
  76.             }
  77.         }
  78.     }
  79.  
  80.     long long laczny_czas = 0;
  81.     bool mozliwe = true;
  82.     vector<long long> wyniki;
  83.  
  84.     for (int i = 0; i < p - 1; ++i) {
  85.         int u1 = przystanki[i];
  86.         int u2 = przystanki[i + 1];
  87.  
  88.         // Obsługa przypadku, gdy stoimy w miejscu (ten sam przystanek/ulica)
  89.         if (u1 == u2) {
  90.             wyniki.push_back(laczny_czas);
  91.             continue;
  92.         }
  93.  
  94.         if (dist[u1][u2] >= INF) {
  95.             mozliwe = false;
  96.             break;
  97.         }
  98.  
  99.         laczny_czas += dist[u1][u2];
  100.         wyniki.push_back(laczny_czas);
  101.     }
  102.  
  103.     if (!mozliwe) {
  104.         cout << "NIE" << endl;
  105.     } else {
  106.         for (long long w : wyniki) {
  107.             cout << w << "\n";
  108.         }
  109.     }
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 6 3
-1 -1
1 -1
1 1
-1 1
1 2 1
2 3 2
3 4 3
4 1 5
2 4 1
1 3 2
1
4
3
stdout
copy 
16
30
https://ideone.com/Mucpqj
language:
C++14 (gcc 8.3)
created:
5 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!