Mostafizur_Rahman

dijkstra_list

Aug 5th, 2021
699
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dis[100];
  4. bool vis[100];
  5. vector<pair<int,int>>adj[100];
  6. priority_queue<pair<int,int>>q;
  7. void process(int x, int n)
  8. {
  9.     for(int i=1; i<=n; i++)
  10.         dis[i]=100000000;
  11.  
  12.     dis[x] = 0;
  13.  
  14.     q.push({0,x});
  15.  
  16.     while(!q.empty())
  17.     {
  18.         int a = q.top().second;
  19.         q.pop();
  20.         if(vis[a])
  21.             continue;
  22.  
  23.         vis[a] = true;
  24.         cout<<a<<" "<<dis[a]<<endl;
  25.         for(auto u : adj[a])
  26.         {
  27.             int b =u.first;
  28.             int w =u.second;
  29.             if(vis[b])
  30.                 continue;
  31.             if(dis[a]+w<dis[b])
  32.             {
  33.                 dis[b]=dis[a]+w;
  34.                 q.push({-dis[b],b});
  35.             }
  36.         }
  37.     }
  38.  
  39.  
  40. }
  41.  
  42. int main()
  43. {
  44.  
  45.     vector<tuple<int,int,int>>edges;
  46.     edges.push_back(make_tuple(1,2,5));
  47.     edges.push_back(make_tuple(1,4,9));
  48.     edges.push_back(make_tuple(1,5,1));
  49.     edges.push_back(make_tuple(3,2,2));
  50.     edges.push_back(make_tuple(3,4,6));
  51.     edges.push_back(make_tuple(4,5,2));
  52.  
  53.     for(auto i:edges)
  54.     {
  55.         adj[get<1>(i)].push_back(make_pair(get<0>(i),get<2>(i)));
  56.         adj[get<0>(i)].push_back(make_pair(get<1>(i),get<2>(i)));
  57.     }
  58.  
  59.     process(1,7);
  60. }
  61.  
RAW Paste Data