Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n,m,a,b;
- long long d;
- bool conf[100010],confdfs[100010];
- vector<pair<long long, int>> adj[100010];
- set<pair<int, int>> prohib;
- priority_queue<pair<long long,pair<int,int>>> pq;
- vector<int> resp;
- bool dfs(int pos){
- confdfs[pos]=true;
- resp.push_back(pos);
- if(pos==1) return true;
- for(int i=0;i<adj[pos].size();i++) if(!confdfs[adj[pos][i].second] && prohib.find({pos,adj[pos][i].second})==prohib.end()) if(dfs(adj[pos][i].second)) return true;
- resp.pop_back();
- return false;
- }
- int main(){
- scanf("%d %d", &n, &m);
- for(int i=0;i<m;i++){
- scanf("%d %d %lld", &a, &b, &d);
- adj[a].push_back({d,b});
- adj[b].push_back({d,a});
- }
- pq.push({0,{1,1}});
- while(!pq.empty()){
- pair<long long, pair<int, int>> h=pq.top();
- pq.pop();
- if(conf[h.second.second]) continue;
- conf[h.second.second]=true;
- prohib.insert(h.second);
- prohib.insert({h.second.second,h.second.first});
- for(int i=0;i<adj[h.second.second].size();i++) pq.push({-h.first-adj[h.second.second][i].first,{h.second.second,adj[h.second.second][i].second}});
- }
- if(dfs(0)){
- printf("%d", resp.size());
- for(int i=0;i<resp.size();i++) printf(" %d", resp[i]);
- printf("\n");
- }
- else printf("impossible\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement