Advertisement
Guest User

Untitled

a guest
Dec 24th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 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. in>>nodi;
  13. vector<pair<int,int>> v[nodi];
  14. in>>archi;
  15. in>>nodoiniziale;
  16. nodoiniziale--;
  17. in>>nododaraggiungere;
  18. nododaraggiungere--;
  19. int a,b,c;
  20. for(int i=0;i<archi;i++){
  21. in>>a;
  22. in>>b;
  23. in>>c;
  24. a--;
  25. b--;
  26. v[a].push_back({b,c});
  27. v[b].push_back({a,c});
  28. }
  29. priority_queue<pair<int,int>> q;
  30. int visitato[nodi];
  31. int distanze[nodi];
  32. for(int i=0;i<nodi;i++){
  33. visitato[i]=0;
  34. distanze[i]=1e9;
  35. }
  36. distanze[nodoiniziale]=0;
  37. q.push({nodoiniziale,0});
  38. int corrente;
  39. while (q.size()!=0||corrente!=nododaraggiungere){
  40. corrente= q.top().first;
  41. q.pop();
  42. if (visitato[corrente]==0){
  43. visitato[corrente] = 1;
  44. for (auto w : v[corrente]) {
  45. if (distanze[corrente]+w.second < distanze[w.first]) {
  46. distanze[w.first] = distanze[corrente]+w.second;
  47. q.push({w.first,-distanze[w.first]});
  48. }
  49. }
  50. }
  51. }
  52. ou<<distanze[nododaraggiungere];
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement