Advertisement
Josif_tepe

Untitled

Feb 20th, 2022
724
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. struct node {
  6.     int idx;
  7.     int shortest_path;
  8.     node() {}
  9.     node(int _idx, int _shortest_path) {
  10.         idx = _idx;
  11.         shortest_path = _shortest_path;
  12.     }
  13.     bool operator < (const node &tmp) const {
  14.         return shortest_path > tmp.shortest_path;
  15.     }
  16. };
  17. int main()
  18. {
  19.     int n, m; // number of nodes and edges
  20.     cin >> n >> m;
  21.    
  22.     vector<pair<int, int> > graph[n + 5];
  23.     for(int i = 0; i < m; i++) {
  24.         int a, b, c;
  25.         cin >> a >> b >> c;
  26.         graph[a].push_back(make_pair(b, c));
  27.         graph[b].push_back(make_pair(a, c));
  28.     }
  29.     int S, E;
  30.     cin >> S >> E;
  31.     priority_queue<node> pq;
  32.     pq.push(node(S, 0));
  33.     vector<bool> visited(n, false);
  34.     while(!pq.empty()) {
  35.         node c = pq.top();
  36.         pq.pop();
  37.         visited[c.idx] = true;
  38.         if(c.idx == E) {
  39.             cout << c.shortest_path << endl;
  40.             break;
  41.         }
  42.         for(int i = 0; i < graph[c.idx].size(); i++) {
  43.             int sosed = graph[c.idx][i].first;
  44.             int rebro = graph[c.idx][i].second;
  45.             if(!visited[sosed]) {
  46.                 pq.push(node(sosed, rebro + c.shortest_path));
  47.             }
  48.            
  49.         }
  50.     }
  51.    
  52.     return 0;
  53. }
  54. /*
  55. 5 6
  56. 0 1 19
  57. 0 2 14
  58. 1 2 20
  59. 2 3 10
  60. 2 4 100
  61. 3 4 13
  62.  
  63.  
  64. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement