Hydron

Untitled

Feb 3rd, 2022 (edited)
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int DIM = 1e4+1;   /// Макс. кількість вершин у графі
  6. const int INF = INT_MAX; /// Величезне число замість нескінченності
  7.  
  8. vector < pair<int,int> > g[DIM]; /// Для кожної вершини зберігаємо ребра як список пар {КУДИ, ЦІНА}
  9.  
  10. void Dijkstra(int s, vector<int> &dist, vector<int> &cnt){
  11.     priority_queue < pair<int,int> > q;
  12.     dist[s] = 0;
  13.     q.push({0, s});
  14.     while(!q.empty()){
  15.         int v = q.top().second, cur_d = -q.top().first; /// second - вершина, в яку заходим, (-1 * first) - найкоротша відстань до неї
  16.         q.pop();
  17.         if (cur_d > dist[v]) continue;
  18.         for (int i=0; i<g[v].size(); i++){
  19.             int to = g[v][i].first, len = g[v][i].second;
  20.             if (dist[v] + len < dist[to]){
  21.                 cnt[to] = 1;
  22.                 dist[to] = dist[v] + len;
  23.                 q.push({-dist[to], to});
  24.             }else{
  25.                 if (dist[v] + len == dist[to]) cnt[to] ++;
  26.             }
  27.         }
  28.     }
  29.     return;
  30. }
  31.  
  32.  
  33. int main(){
  34.     int n, m, k, a, b, c;
  35.     scanf("%d %d %d", &n, &m, &k);
  36.     vector < int > path;
  37.     for (int i=0; i<k; i++){
  38.         scanf("%d", &a);
  39.         path.push_back(a);
  40.     }
  41.     for (int i=0; i<m; i++){
  42.         scanf("%d %d %d", &a, &b, &c);
  43.         g[a].push_back({b, c});
  44.         g[b].push_back({a, c});
  45.     }
  46.     vector < int > d1(n+1, INF), c1(n+1, 0);
  47.     Dijkstra(1, d1, c1);
  48.     for (int i=0; i<k; i++){
  49.         if (c1[path[i]] > 1) {printf("yes\n"); return 0;}
  50.     }
  51.     printf("no\n");
  52.     return 0;
  53. }
  54.  
Add Comment
Please, Sign In to add comment