Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int DIM = 1e4+1; /// Макс. кількість вершин у графі
- const int INF = INT_MAX; /// Величезне число замість нескінченності
- vector < pair<int,int> > g[DIM]; /// Для кожної вершини зберігаємо ребра як список пар {КУДИ, ЦІНА}
- void Dijkstra(int s, vector<int> &dist, vector<int> &cnt){
- priority_queue < pair<int,int> > q;
- dist[s] = 0;
- q.push({0, s});
- while(!q.empty()){
- int v = q.top().second, cur_d = -q.top().first; /// second - вершина, в яку заходим, (-1 * first) - найкоротша відстань до неї
- q.pop();
- if (cur_d > dist[v]) continue;
- for (int i=0; i<g[v].size(); i++){
- int to = g[v][i].first, len = g[v][i].second;
- if (dist[v] + len < dist[to]){
- cnt[to] = 1;
- dist[to] = dist[v] + len;
- q.push({-dist[to], to});
- }else{
- if (dist[v] + len == dist[to]) cnt[to] ++;
- }
- }
- }
- return;
- }
- int main(){
- int n, m, k, a, b, c;
- scanf("%d %d %d", &n, &m, &k);
- vector < int > path;
- for (int i=0; i<k; i++){
- scanf("%d", &a);
- path.push_back(a);
- }
- for (int i=0; i<m; i++){
- scanf("%d %d %d", &a, &b, &c);
- g[a].push_back({b, c});
- g[b].push_back({a, c});
- }
- vector < int > d1(n+1, INF), c1(n+1, 0);
- Dijkstra(1, d1, c1);
- for (int i=0; i<k; i++){
- if (c1[path[i]] > 1) {printf("yes\n"); return 0;}
- }
- printf("no\n");
- return 0;
- }
Add Comment
Please, Sign In to add comment