Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int,int> > G[100500];
  4. vector<int> exits;
  5. int n, m, k;
  6. int dijkstra(int at)
  7. {
  8.     priority_queue<pair<int,int> > pq;
  9.     pq.push(make_pair(0,at));
  10.     vector<int> dist;
  11.     dist.resize(n);
  12.     for(int i=0;i<n;i++)
  13.         dist[i] = 1e9;
  14.     bool vis[n][2];
  15.     memset(vis,false,sizeof(vis));
  16.     for(int i=0;i<exits.size();i++)
  17.         vis[exits[i]][0] = true;
  18.     dist[0] = 0;
  19.     while(!pq.empty())
  20.     {
  21.         pair<int,int> state = pq.top();
  22.         pq.pop();
  23.         int city = state.second;
  24.         int path = -state.first;
  25.         if(city == 0 && vis[city][0] == true)
  26.             break;
  27.         if(vis[city][0] == false)
  28.         {
  29.             cout<<city<<" "<<path<<endl;
  30.             vis[city][0] = true;
  31.             vector<pair<int,int> > can_go = G[city];
  32.             for(int i=0;i<can_go.size();i++)
  33.             {
  34.                 int next = can_go[i].first;
  35.                 int dist_between = can_go[i].second;
  36.                 if(dist[next] > dist[city] + dist_between && vis[next][0] == false)
  37.                 {
  38.                     dist[next] = dist[city] + dist_between;
  39.                     pq.push(make_pair(-dist[next], next));
  40.                 }
  41.                 else if(vis[next][0] == true)
  42.                     dist[next] = dist[city] + dist_between;
  43.             }
  44.         }
  45.         if(vis[city][1] == false)
  46.             continue;
  47.     }
  48.     int naj = -1;
  49.     int sec_naj = -1;
  50.     for(int i=0;i<exits.size();i++)
  51.     {
  52.         if(dist[exits[i]] >= naj)
  53.         {
  54.             sec_naj = naj;
  55.             naj = dist[exits[i]];
  56.         }
  57.     }
  58.         return sec_naj;
  59. }
  60. int main()
  61. {
  62.    
  63.     cin>>n>>m>>k;
  64.     for(int i=0;i<m;i++)
  65.     {
  66.         int from, to, weigh;
  67.         cin>>from>>to>>weigh;
  68.         G[from].push_back(make_pair(to,weigh));
  69.         G[to].push_back(make_pair(from,weigh));
  70.     }
  71.    
  72.     for(int i=0;i<k;i++)
  73.     {
  74.         int a;
  75.         cin>>a;
  76.         exits.push_back(a);
  77.     }
  78.     cout<<dijkstra(0)<<endl;
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement