SHARE
TWEET

parc

a guest May 23rd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. ifstream in ("parc.in");
  5. ofstream out ("parc.out");
  6.  
  7. #define INF 1000000000
  8. #define MAXN 102
  9. priority_queue <pair <int, int> > q;
  10. vector <pair <int, int> >g[MAXN+1];
  11. int dist[MAXN+1];
  12. int v[MAXN];
  13.  
  14. int n;
  15.  
  16. void dijkstra(int start) {
  17.     int son, node, cost, dist_son, i;
  18.     for(i=1; i<=n; i++)
  19.         dist[i]=INF;
  20.     dist[start]=0;
  21.     q.push({0, start});
  22.     while(!q.empty()) {
  23.         cost=-q.top().first;
  24.         node=q.top().second;
  25.         q.pop();
  26.         if(cost<=dist[node])
  27.             for(i=0; i<g[node].size(); i++) {
  28.                 dist_son=-g[node][i].first;
  29.                 son=g[node][i].second;
  30.                 if(dist[son]>dist_son+cost) {
  31.                     dist[son]=dist_son+cost;
  32.                     q.push({-dist[son], son});
  33.                 }
  34.             }
  35.     }
  36.  
  37. }
  38.  
  39. int main()
  40. {
  41.     int m, a, b, c, cost, p, i, poarta, minim;
  42.  
  43.     in>>n>>m>>c;
  44.     for(i=0; i<m; i++) {
  45.        in>>a>>b>>cost;
  46.         g[a].push_back({-cost, b});
  47.     }
  48.     in>>p;
  49.     for(i=0; i<p; i++)
  50.         in>>v[i];
  51.  
  52.     dijkstra(c);
  53.     minim=INF;
  54.     for(i=0; i<p; i++) {
  55.         if(dist[v[i]]==INF)
  56.             dist[v[i]]=0;
  57.         if(dist[v[i]]<minim) {
  58.             minim=dist[v[i]];
  59.             poarta=v[i];
  60.         }
  61.     }
  62.     out<<poarta;
  63.  
  64.     return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top