fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN=1e5+5;
  5.  
  6. long long n,m;
  7. vector<pair<long long,long long>> arr[MaxN];
  8. long long dis[MaxN];
  9.  
  10. void bfs(long long x, vector<pair<long long,long long>> arr[], bool visited[], long long dis[])
  11. {
  12.     for(long long i=1; i<=n; i++)
  13.     {
  14.         visited[i]=false;
  15.         dis[i]=0;
  16.     }
  17.  
  18.     queue<long long> qu;
  19.  
  20.     qu.push(x);
  21.     visited[x]=true;
  22.  
  23.     while(!qu.empty())
  24.     {
  25.         long long u=qu.front();
  26.         qu.pop();
  27.  
  28.         for(auto fi:arr[u])
  29.         {
  30.             long long v=fi.first;
  31.  
  32.             if(!visited[v])
  33.             {
  34.                 visited[v]=true;
  35.                 dis[v]=dis[u]+1;
  36.                 qu.push(v);
  37.             }
  38.         }
  39.     }
  40. }
  41.  
  42. void bfs(long long x, vector<pair<long long,long long>> arr[], bool visited[], vector<long long> &ans)
  43. {
  44.     queue<long long> qu;
  45.     qu.push(x);
  46.  
  47.     while(!qu.empty())
  48.     {
  49.         long long sz=qu.size();
  50.         long long mn=LLONG_MAX;
  51.  
  52.         for(long long i=1; i<=sz; i++)
  53.         {
  54.             long long u=qu.front();
  55.             qu.pop();
  56.  
  57.             if(u==n)
  58.             {
  59.                 return;
  60.             }
  61.  
  62.             for(auto fi:arr[u])
  63.             {
  64.                 long long v=fi.first;
  65.                 long long w=fi.second;
  66.  
  67.                 if(dis[v]==dis[u]-1)
  68.                 {
  69.                     mn=min(mn,w);
  70.                 }
  71.             }
  72.  
  73.             qu.push(u);
  74.         }
  75.  
  76.         if(mn==LLONG_MAX)
  77.         {
  78.             return;
  79.         }
  80.  
  81.         ans.push_back(mn);
  82.  
  83.         for(long long i=1; i<=sz; i++)
  84.         {
  85.             long long u=qu.front();
  86.             qu.pop();
  87.  
  88.             for(auto fi:arr[u])
  89.             {
  90.                 long long v=fi.first;
  91.                 long long w=fi.second;
  92.  
  93.                 if(dis[v]==dis[u]-1 && w==mn)
  94.                 {
  95.                     qu.push(v);
  96.                 }
  97.             }
  98.         }
  99.     }
  100. }
  101.  
  102. void input()
  103. {
  104.     cin>>n>>m;
  105.  
  106.     for(long long i=1; i<=m; i++)
  107.     {
  108.         long long u,v,w;
  109.  
  110.         cin>>u>>v>>w;
  111.  
  112.         arr[u].push_back({v,w});
  113.         arr[v].push_back({u,w});
  114.     }
  115. }
  116.  
  117. void solve()
  118. {
  119.     bool visited[MaxN];
  120.     vector<long long> ans;
  121.  
  122.     bfs(n,arr,visited,dis);
  123.  
  124.     bfs(1,arr,visited,ans);
  125.  
  126.     cout<<dis[1]<<'\n';
  127.  
  128.     for(long long x:ans)
  129.     {
  130.         cout<<x<<' ';
  131.     }
  132. }
  133.  
  134. int main()
  135. {
  136.     ios_base::sync_with_stdio(0);
  137.     cin.tie(0);
  138.  
  139.     input();
  140.     solve();
  141. }
Success #stdin #stdout 0.01s 5956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/P0XRGF
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!