Advertisement
Guest User

parc

a guest
May 23rd, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.34 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement