Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- __Allahu Akbar__
- __All_praises_to_Allah__
- __Bismillahir_Rahmanir_Rahim__
- Author: Abdullah Al Nayem
- Studying B.Sc in CSE at Leading University.
- Practice, like you've never won. Perform, like you've never lost.
- Practice hard, play hard. Be hard to beat.
- */
- #include <bits/stdc++.h>
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <math.h>
- #include <bitset>
- using namespace std;
- #define MAX 100007
- #define ll long long
- #define pb push_back
- #define mkp make_pair
- #define F first
- #define S second
- #define Sort_arr(arr,x) sort(arr,arr+x)
- #define Sortr_arr(arr,x) sort(arr, arr+n,greater<int>())
- #define SortS(str) sort(str.begin(), str.end())
- #define SortRS(str) sort(str.rbegin(), str.rend())
- #define arr_rev(n) sort(n.begin(), n.end(), greater<int>())
- #define gin(a) getline(cin,a)
- #define Sz(a) a.size()
- #define Ignore cin.ignore()
- #define sq(n) (n*n)
- #define cube(n) (n*n*n)
- #define min3(a, b, c) min(a, min(b, c))
- #define max3(a, b, c) max(a, max(b, c))
- #define YES cout << "YES" << endl
- #define NO cout << "NO" << endl
- #define pYES printf("YES\n")
- #define pNO printf("NO\n")
- #define bs binary_search
- #define lb lower_bound
- #define ub upper_bound
- #define all(a) a.begin(),a.end()
- #define Fast_read ios_base::sync_with_stdio(false);
- //#define SIZE_N 32000
- //bitset <SIZE_N> bs;
- //ll int primes[SIZE_N+5];
- //vector<int> primes;
- /*-----------------------Useful functions-----------------------*/
- //ll int seive(){ll int i,j,total=0,val;for(i=2;i<=SIZE_N;i++) bs[i]=1;val=sqrt(SIZE_N)+1;for(i=2;i<val;i++)if(bs[i])for(j=i;j*i<=SIZE_N;j++)bs[i*j]=0;for(i=2;i<=SIZE_N;i++)if(bs[i])primes[total++]=i;return total;}
- //void Sseive() {bool isPrime[MAX];for (int i = 0; i < MAX; ++i) isPrime[i] = true;for (int i = 3; i * i <= MAX; i += 2) {if (isPrime[i]) {for (int j = i * i; j <= MAX; j += i) {isPrime[j] = false;}}}primes.push_back(2);for (int i = 3; i < MAX; i += 2) {if (isPrime[i]) primes.push_back(i);}}void segSieve (ll l, ll r) {bool isPrime[r-l+1];for (int i = 0; i < r - l + 1; ++i) isPrime[i] = true;if (l == 1) isPrime[0] = false;for (int i = 0; primes[i]*primes[i] <= r; ++i) {int currentPrime = primes[i];ll base = (l/currentPrime)*currentPrime;if (base < l) base += currentPrime;for (ll j = base; j <= r; j += currentPrime) {isPrime[j-l] = false;}if (base == currentPrime) isPrime[base-l] = true;}for (int i = 0; i < r - l + 1; ++i) {if (isPrime[i]) cout << (i+l) << endl;}puts("");}
- //ll int divisor_mcs(ll int N){ll int count=0,i;for (i=1;i<=sqrt(N);i++){if (N%i==0){count++;if (N/i!=i) count++;}}return count;}
- //int divisor(int N){int i,val,count,sum;val=sqrt(N)+1;sum=1;for(i=0;primes[i]<val;i++){if(N%primes[i]==0){count=0;while(N%primes[i]==0){N/=primes[i];count++;}sum*=(count+1);}}if(N>1)sum=sum*2;return sum;}
- //vector <int> primefactor(int n){int i;vector<int> primefact;for (i=2;i<=sqrt(n);i++){if (n%i==0){int count=0;while(n%i==0){n=n/i;count++;}while(count>0){primefact.pb(i);count--;}}}if (n!=1) primefact.pb(n);return primefact;}
- //vector <int> all_divisor(int n){int i;vector<int> all_div;for (i=2;i<=sqrt(n);i++){if (n%i==0) all_div.pb(i);if (n/i!=i && n%i==0) all_div.pb(n/i);}sort(all_div.begin(),all_div.end());return all_div;}
- //ll int GCD (ll int x, ll int y){if (x%y==0) return y; else return (GCD(y,x%y));}
- //ll int LCM (ll int a,ll int b) {return (a/GCD(a,b))*b;}
- //bool is_prime(ll int n){for (ll int i=2;i<=sqrt(n);i++){if (n%i==0) return false;}return true;}
- /*------------------------------------------------------------------*/
- # define INF 0x3f3f3f3f
- ll n,m;
- vector <pair<ll,ll>> adj[MAX];
- void printPath(ll parent[], ll j)
- {
- if (parent[j] == - 1)
- return;
- printPath(parent, parent[j]);
- cout<<j+1<<" ";
- }
- ll havePath(vector<ll> dis,ll parent[])
- {
- ll src = 1;
- if (parent[n-1]==-1)
- {
- cout<<-1<<endl;
- return 0;
- }
- else
- {
- cout<<1<<" ";
- printPath(parent, n-1);
- }
- }
- void STP(ll src,ll V)
- {
- priority_queue< pair<ll, ll>, vector <pair<ll, ll>> , greater<pair<ll, ll>> > pq;
- vector<ll> dis(V, INF);
- pq.push(make_pair(0, src));
- dis[src] = 0;
- ll parent[V];
- for (int i=0;i<V;i++)
- {
- parent[i]=-1;
- }
- while (!pq.empty())
- {
- ll u = pq.top().second;
- pq.pop();
- for (auto x : adj[u])
- {
- ll v = x.first;
- ll weight = x.second;
- if (dis[v] > dis[u] + weight)
- {
- dis[v] = dis[u] + weight;
- parent[v] = u;
- pq.push(make_pair(dis[v], v));
- }
- }
- }
- havePath(dis, parent);
- }
- int main()
- {
- //seive();
- //freopen("Nayem.txt", "r", stdin);
- Fast_read
- cin>>n>>m;
- for (int i=0;i<m;i++)
- {
- ll a,b,w;
- cin>>a>>b>>w;
- adj[a-1].pb(make_pair(b-1,w));
- adj[b-1].pb(make_pair(a-1,w));
- }
- STP(0,n);
- return 0;
- }
Add Comment
Please, Sign In to add comment