Advertisement
Guest User

Untitled

a guest
Dec 24th, 2018
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<fstream>
  5. using namespace std;
  6. int main(){
  7. ifstream in;
  8. ofstream ou;
  9. in.open("input.txt");
  10. ou.open("output.txt");
  11. int nodi,archi,nodoiniziale,nododaraggiungere;
  12. priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
  13. in>>nodi;
  14. in>>archi;
  15. in>>nodoiniziale;
  16. in>>nododaraggiungere;
  17. nodoiniziale--;
  18. nododaraggiungere--;
  19. int a,b,c;
  20. vector<pair<int,int>> v[nodi];
  21. for(int i=0;i<archi;i++){
  22. in>>a;
  23. in>>b;
  24. in>>c;
  25. a--;
  26. b--;
  27. v[a].push_back({b,c});
  28. v[b].push_back({a,c});
  29. }
  30. int visitato[nodi];
  31. int distanze[nodi];
  32. for(int i=0;i<nodi;i++){
  33. distanze[i]=1e9;
  34. visitato[i]=0;
  35. }
  36. distanze[nodoiniziale]=0;
  37. q.push({0,nodoiniziale});
  38. int corrente;
  39. while(!q.empty()){
  40. corrente=q.top().second;
  41. q.pop();
  42. if(visitato[corrente]==0){
  43. visitato[corrente]=1;
  44. for(auto y:v[corrente]){
  45. if(distanze[corrente]+y.second<distanze[y.first]){
  46. distanze[y.first]=distanze[corrente]+y.second;
  47. q.push({distanze[y.first],y.first});
  48. }
  49. }
  50. }
  51. }
  52. ou<<distanze[nododaraggiungere];
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement