TAHMID37

Dijkstra

Dec 5th, 2021
523
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*  TAHMID RAHMAN
  2.     DAMIAN FOREVER
  3.      MATH LOVER
  4.     NEVER GIVE UP
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define pi acos(-1.0)
  9. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. #define ll long long
  11. #define pb push_back
  12. #define fi first
  13. #define se second
  14. #define in insert
  15. #define mp make_pair
  16. #define GCD(a,b) __gcd(a,b);
  17. #define endl "\n"
  18. #define FRU freopen("out.txt","w",stdout)
  19. #define FRO freopen("in.txt","r",stdin)
  20. #define INFLL 9223372036854775807
  21. #define all(x) (x).begin(),(x).end()
  22. #define MAXN   100001
  23. #define ar array
  24. #define lb lower_bound
  25. #define ub upper_bound
  26. #define minpq priority_queue<ll, vector<ll>, greater<ll>>
  27. #define maxpq priority_queue<ll>
  28. const int mxN=2e5;
  29. const int MOD=1e9+7;
  30. template<typename ForwardIterator, typename T>
  31. ForwardIterator first_less_than (ForwardIterator first, ForwardIterator last, T value)
  32. {auto it = std::lower_bound (first, last, value);
  33. return (it == first ? last : --it);}
  34. bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b)
  35. {
  36.     return (a.second < b.second);
  37. }
  38. #define debugxx(v) {for(auto x:v){cout<<x.fi<<" "<<x.se<<endl;}cout<<endl;}
  39. #define debugx(v){for(auto y:v) {cout<<y<<" ";}cout<<endl;}
  40. #define debug(x) cout<<#x<<" ";_print(x); cout<<endl;
  41. typedef unsigned long long ull;
  42. typedef long double lld;
  43. void _print(ll t) {cout << t;}
  44. void _print(int t) {cout << t;}
  45. void _print(string t) {cout << t;}
  46. void _print(char t) {cout << t;}
  47. void _print(lld t) {cout << t;}
  48. void _print(double t) {cout << t;}
  49. void _print(ull t) {cout << t;}
  50.  
  51. template <class T, class V> void _print(pair <T, V> p);
  52. template <class T> void _print(vector <T> v);
  53. template <class T> void _print(set <T> v);
  54. template <class T, class V> void _print(map <T, V> v);
  55. template <class T> void _print(multiset <T> v);
  56. template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.fi); cout << ","; _print(p.se); cout << "}";}
  57. template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
  58. template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
  59. template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
  60. template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
  61. //Don't hesitate to ask me if you don't understand my code.......Happy coding,Tahmid...;
  62.  
  63. vector<ll>adj[mxN];
  64. vector<ll>cost[mxN];
  65. ll dis[mxN];
  66.  
  67. void dijkstra(ll s)
  68. {
  69.     priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
  70.     for(ll i=0;i<mxN;i++)
  71.         dis[i]=INFLL;
  72.     dis[s]=0;
  73.  
  74.     pq.push({dis[s],s});
  75.  
  76.     while(pq.size())
  77.     {
  78.         pair<ll,ll>top=pq.top();
  79.         ll d=top.fi;
  80.         ll node=top.se;
  81.         pq.pop();
  82.  
  83.         for(ll i=0;i<adj[node].size();i++)
  84.         {
  85.             if(dis[node]+cost[node][i]<dis[adj[node][i]])
  86.             {
  87.  
  88.                 dis[adj[node][i]]=dis[node]+cost[node][i];
  89.                 pq.push({dis[adj[node][i]],adj[node][i]});
  90.  
  91.             }
  92.         }
  93.  
  94.     }
  95.  
  96.  
  97. }
  98.  
  99. void add(ll a, ll b,ll c)
  100. {
  101.     adj[a].pb(b);
  102.     adj[b].pb(a);
  103.     cost[a].pb(c);
  104.     cost[b].pb(c);
  105. }
  106.  
  107. int main()
  108. {
  109.     fastio;
  110.  
  111.     add(0,1,4);
  112.     add(0,7,8);
  113.     add(1,2,8);
  114.     add(1,7,11);
  115.     add(2,3,7);
  116.     add(2,8,2);
  117.     add(2,5,4);
  118.     add(3,4,9);
  119.     add(3,5,14);
  120.     add(4,5,10);
  121.     add(5,6,2);
  122.     add(6,7,1);
  123.     add(6,8,6);
  124.     add(7,8,7);
  125.  
  126.     dijkstra(0);
  127.  
  128.  
  129.     for(ll i=0;i<=8;i++)
  130.     {
  131.         cout<<i<<" "<<dis[i]<<endl;
  132.     }
  133.  
  134. }
  135.  
  136.  
  137.  
  138.  
RAW Paste Data