Advertisement
Guest User

Untitled

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