fork download
copy 
  1. /// Construct a palindrome Atcoder
  2. /// Author: PmQwerty
  3. #include<bits/stdc++.h>
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7. const int MAXN = 1010;
  8. const int INF = 1e9;
  9. int n, m;
  10. int dist[MAXN][MAXN];
  11. vector<pair<int, char>> a[MAXN];
  12. int main(){
  13.     ios_base::sync_with_stdio(0);
  14.     cin.tie(0);
  15.     cin >> n >> m;
  16.     for (int i = 1; i <= m; i++){
  17.          int u, v;
  18.          char c;
  19.          cin >> u >> v >> c;
  20.          a[u].push_back({v, c});
  21.          a[v].push_back({u, c});
  22.     }
  23.     for (int i = 1; i <= n; i++){
  24.          for (int j = 1; j <= n; j++){
  25.               dist[i][j] = INF;
  26.          }
  27.     }
  28.     queue<pair<int, int>> f;
  29.     for (int u = 1; u <= n; u++){
  30.         f.push({u, u});
  31.         dist[u][u] = 0;
  32.         for (pair<int, char> v: a[u]){
  33.              if (dist[u][v.fi] == INF){
  34.                  dist[u][v.fi] = dist[v.fi][u] = 1;
  35.                  f.push({u, v.fi});
  36.              }
  37.         }
  38.     }
  39.     bool check = false;
  40.     while (!f.empty()){
  41.          pair<int, int> cur = f.front();
  42.          f.pop();
  43.          if ((cur.fi == 1 && cur.se == n) || (cur.se == 1 && cur.fi == n)){
  44.              check = true;
  45.              break;
  46.          }
  47.          int p = dist[cur.fi][cur.se] + 2;
  48.          for (pair<int, char> v1: a[cur.fi]){
  49.               for (pair<int, char> v2: a[cur.se]){
  50.                    if (v1.se == v2.se && p < dist[v1.fi][v2.fi]){
  51.                        dist[v1.fi][v2.fi] = dist[v2.fi][v1.fi] = p;
  52.                        f.push({v1.fi, v2.fi});
  53.                    }
  54.               }
  55.          }
  56.     }
  57.     cout << (check ? dist[1][n] : -1) << '\n';
  58. }
  59.  
Success #stdin #stdout 0.01s 5252KB
comments (?)
stdin
copy 
8 8
1 2 a
2 3 b
1 3 c
3 4 b
4 5 a
5 6 c
6 7 b
7 8 a
stdout
copy 
10
https://ideone.com/RHHM1F
language:
C++14 (gcc 8.3)
created:
12 days 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!