Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<long,long> pl;
- typedef pair<ll,ll> pll;
- typedef vector<long> vl;
- typedef vector<bool> vb;
- typedef vector<ll> vll;
- typedef vector<vl> vvl;
- typedef vector<vb> vvb;
- typedef vector<vll> vvll;
- typedef vector<pll> vpll;
- typedef vector<string> vs;
- #define FOR(i,a,b) for(long long i=a;i<b;++i)
- #define REV(i,a,b) for(long long i=a;i>=b;i--)
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- #define all(v) v.begin(),v.end()
- #define tc ll t;cin>>t;while(t--)
- #define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
- #define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
- #define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
- #define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
- #define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
- #define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
- #define newl cout<<"\n"
- #define mod 1000000007
- #define INF 100000000009
- ll n,m;
- vector< vector<pair<ll,ll> > >g;
- vector<ll> dist,par;//out
- //vector<bool> vis(n);//out
- void dijk(ll p);
- int main()
- {
- io;
- ll a,b,w;
- cin>>n>>m;
- g.resize(n+1);
- par.resize(n+1,-1);
- par[1]=1;
- dist.resize(n+1,INF);
- FOR(i,0,m)
- {
- cin>>a>>b>>w;
- if(a==b){continue;}
- g[a].pb({b,w});
- g[b].pb({a,w});
- }
- if(par[n]==-1){cout<<"-1";}
- else
- {
- vll ans;
- ans.pb(n);
- ll x=n;
- while(x!=1)
- {
- x=par[x];
- ans.pb(x);
- }
- reverse(all(ans));
- coutv(ans);
- }
- return 0;
- }
- void dijk(ll p)
- {
- priority_queue< pair<ll,ll> > q;
- dist[p]=0;
- q.push({0,p});
- while(!q.empty())
- {
- ll a=q.top().S;
- q.pop();
- /*if(vis[a]){continue;}
- vis[a]=true;*/
- for(auto v: g[a])
- {
- ll b=v.F,w=v.S;
- if(dist[a]+w<dist[b])
- {
- dist[b]=dist[a]+w;
- par[b]=a;
- q.push({-dist[b],b});
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement