fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define int ll
  7. #define endl '\n'
  8. #define vll vector<ll>
  9. #define input(arr) \
  10.     for (auto& i : arr) cin >> i
  11. #define print(arr) \
  12.     for (auto& i : arr) cout << i << ' '; cout << '\n'
  13. #define INF LLONG_MAX
  14. #define YARAB_ACCEPT ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  15.  
  16. ll dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
  17. ll dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
  18. const ll N = 2e5 + 5;
  19.  
  20. struct Edge { ll to; char c; };
  21.  
  22. vector<Edge> adj[N];
  23.  
  24. void solve() {
  25.     ll n, m; cin >> n >> m;
  26.  
  27.     for (ll i = 0; i < m; ++i) {
  28.         ll u, v; cin >> u >> v;
  29.         char c; cin >> c;
  30.         adj[u].push_back({v, c});
  31.         adj[v].push_back({u, c});
  32.     }
  33.  
  34.     vll dist(n + 1, -1);
  35.     queue<ll> q;
  36.     dist[n] = 0;
  37.     q.push(n);
  38.  
  39.     while (!q.empty()) {
  40.         ll u = q.front(); q.pop();
  41.  
  42.         for (const auto& edge : adj[u]) {
  43.             if (dist[edge.to] == -1) {
  44.                 dist[edge.to] = dist[u] + 1;
  45.                 q.push(edge.to);
  46.             }
  47.         }
  48.     }
  49.  
  50.     vll curr = {1}, parent(n + 1, -1), vis(n + 1, false);
  51.     string s = "";
  52.     vis[1] = 1;
  53.  
  54.     for (int step = 0; step < dist[1]; ++step) {
  55.         char min_char = 'z' + 1;
  56.  
  57.         for (auto u : curr) {
  58.             for (const auto& edge : adj[u]) {
  59.                 if (dist[edge.to] == dist[u] - 1) {
  60.                     min_char = min(min_char, edge.c);
  61.                 }
  62.             }
  63.         }
  64.  
  65.         s.push_back(min_char);
  66.  
  67.         vll next_curr;
  68.  
  69.         for (auto u : curr) {
  70.             for (const auto& edge : adj[u]) {
  71.                 if (dist[edge.to] == dist[u] - 1 && edge.c == min_char) {
  72.                     if (!vis[edge.to]) {
  73.                         vis[edge.to] = 1;
  74.                         parent[edge.to] = u;
  75.                         next_curr.push_back(edge.to);
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.  
  81.         swap(curr, next_curr);
  82.     }
  83.  
  84.     vll path;
  85.     ll curr_node = n;
  86.  
  87.     while (curr_node != -1) {
  88.         path.push_back(curr_node);
  89.         curr_node = parent[curr_node];
  90.     }
  91.     reverse(path.begin(), path.end());
  92.  
  93.     cout << dist[1] << '\n';
  94.  
  95.     for (ll i = 0; i < path.size(); ++i) {
  96.         cout << path[i] << ' ';
  97.     }
  98.  
  99.     cout << '\n';
  100.     cout << s << '\n';
  101. }
  102.  
  103. signed main() {
  104.     YARAB_ACCEPT
  105.     ll t = 1;
  106.     // cin >> t;
  107.     while (t--)
  108.         solve();
  109.  
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 8236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/Irqpzh
language:
C++ (gcc 8.3)
created:
1 day 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!