Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n;
- const int MAX=1e5+10;
- int dist[MAX],par[MAX];
- #define ii pair<int,int>
- vector< ii > adjlist[MAX];
- bitset<MAX>visited;
- bool Dijstra(int start, int endd)
- {
- fill(dist,dist+endd+2,INFINITY);
- priority_queue<ii,vector<ii>,greater<ii> >pq;
- pq.push(ii(0,start));
- dist[start]=0;
- par[start]=-1;
- while(!pq.empty())
- {
- int u= pq.top().second;
- pq.pop();
- if(u==endd)return true;
- visited[u]=true;
- for(auto &pr : adjlist[u])
- {
- int v=pr.first;
- int weight=pr.second;
- if(!visited[v] && dist[u]+weight<dist[v])
- {
- dist[v]=dist[u]+weight;
- pq.push(ii(dist[v],v));
- par[v]=u;
- }
- }
- }
- return false;
- }
- int main()
- {
- int edge;
- scanf("%d %d",&n,&edge);
- while(edge--)
- {
- int u,v,weight;
- scanf("%d %d %d",&u,&v,&weight);
- adjlist[u].push_back(ii(v,weight));
- adjlist[v].push_back(ii(u,weight));
- }
- if(Dijstra(1,n))
- {
- vector<int>path;
- for(edge=n;edge!=-1;edge=par[edge])path.push_back(edge);
- for(int i=path.size()-1;i>0;i--)cout<<path[i]<<" ";
- printf("%d\n",path[0]);
- }
- else printf("-1\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement