fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using pii = pair<int,int>;
  4. const int INF = 1e9;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, m;
  11.     if (!(cin >> n >> m)) return 0;
  12.     vector<vector<pair<int,int>>> out(n+1); // out[u] = list of (v, color)
  13.     vector<tuple<int,int,int>> edges;
  14.     edges.reserve(m);
  15.     for (int i = 0; i < m; ++i) {
  16.         int u, v, c;
  17.         cin >> u >> v >> c;
  18.         edges.emplace_back(u,v,c);
  19.         out[u].push_back({v,c});
  20.     }
  21.  
  22.     if (n == 1) { // already at destination
  23.         cout << 0 << '\n';
  24.         return 0;
  25.     }
  26.  
  27.     // For each node v, collect set of incoming colors (colors of edges that end at v)
  28.     vector<unordered_map<int,int>> color_id(n+1);
  29.     color_id.assign(n+1, unordered_map<int,int>());
  30.  
  31.     for (auto &t : edges) {
  32.         int u,v,c;
  33.         tie(u,v,c) = t;
  34.         if (color_id[v].find(c) == color_id[v].end()) {
  35.             int id = (int)color_id[v].size();
  36.             color_id[v][c] = id;
  37.         }
  38.         // Note: we don't need colors for u unless there is incoming edge to u
  39.     }
  40.  
  41.     // assign global ids to each (v, color)
  42.     vector<int> base_index(n+1, 0); // base_index[v] = starting id for node v in dist array
  43.     int total_states = 0;
  44.     for (int v = 1; v <= n; ++v) {
  45.         base_index[v] = total_states;
  46.         total_states += (int)color_id[v].size();
  47.     }
  48.     if (total_states == 0) {
  49.         // no edge enters any node => impossible unless n==1 (handled)
  50.         cout << -1 << '\n';
  51.         return 0;
  52.     }
  53.  
  54.     auto get_state = [&](int v, int color) -> int {
  55.         auto it = color_id[v].find(color);
  56.         if (it == color_id[v].end()) return -1;
  57.         return base_index[v] + it->second;
  58.     };
  59.  
  60.     vector<int> dist(total_states, INF);
  61.     deque<int> dq;
  62.  
  63.     // Initialize: from node 1 (no previous color), taking any outgoing edge (1->v,color)
  64.     // leads to state (v,color) with cost 0 (first edge never counts as a color-change).
  65.     for (auto &p : out[1]) {
  66.         int v = p.first;
  67.         int c = p.second;
  68.         int sid = get_state(v, c);
  69.         if (sid == -1) continue; // shouldn't happen but safe
  70.         if (dist[sid] > 0) {
  71.             dist[sid] = 0;
  72.             dq.push_front(sid);
  73.         }
  74.     }
  75.  
  76.     // 0-1 BFS over states
  77.     while (!dq.empty()) {
  78.         int cur = dq.front(); dq.pop_front();
  79.         int curd = dist[cur];
  80.         // decode cur -> (u,color_prev)
  81.         // We need to know which node u this state belongs to and the color value.
  82.         // To decode, find node v such that base_index[v] <= cur < base_index[v] + color_id[v].size()
  83.         // We'll binary search over base_index since base_index is monotonic.
  84.         // Simpler: build reverse mapping arrays of state -> (node, color_value).
  85.         break;
  86.     }
  87.  
  88.     // Because we need decode, rebuild reverse arrays:
  89.     vector<int> state_node(total_states), state_color(total_states);
  90.     for (int v = 1; v <= n; ++v) {
  91.         for (auto &kv : color_id[v]) {
  92.             int color = kv.first;
  93.             int idx = kv.second;
  94.             int sid = base_index[v] + idx;
  95.             state_node[sid] = v;
  96.             state_color[sid] = color;
  97.         }
  98.     }
  99.  
  100.     // Reinitialize dist and deque, then run proper BFS
  101.     fill(dist.begin(), dist.end(), INF);
  102.     dq.clear();
  103.     for (auto &p : out[1]) {
  104.         int v = p.first, c = p.second;
  105.         int sid = get_state(v, c);
  106.         if (sid == -1) continue;
  107.         if (dist[sid] > 0) {
  108.             dist[sid] = 0;
  109.             dq.push_front(sid);
  110.         }
  111.     }
  112.  
  113.     while (!dq.empty()) {
  114.         int cur = dq.front(); dq.pop_front();
  115.         int curd = dist[cur];
  116.         int u = state_node[cur];
  117.         int color_prev = state_color[cur];
  118.  
  119.         // from (u, color_prev) try all outgoing edges (u -> v, c)
  120.         for (auto &e : out[u]) {
  121.             int v = e.first;
  122.             int c = e.second;
  123.             int nxt = get_state(v, c);
  124.             if (nxt == -1) continue; // state not present (shouldn't happen)
  125.             int add = (c == color_prev) ? 0 : 1;
  126.             if (dist[nxt] > curd + add) {
  127.                 dist[nxt] = curd + add;
  128.                 if (add == 0) dq.push_front(nxt);
  129.                 else dq.push_back(nxt);
  130.             }
  131.         }
  132.     }
  133.  
  134.     // answer = min dist over all states that correspond to node n
  135.     int best = INF;
  136.     if (!color_id[n].empty()) {
  137.         for (auto &kv : color_id[n]) {
  138.             int sid = base_index[n] + kv.second;
  139.             best = min(best, dist[sid]);
  140.         }
  141.     }
  142.     // Also consider direct edge 1->n: we initialized those states with 0 already; if there is no incoming color to n (no edges into n),
  143.     // then impossible. (Handled above)
  144.     if (best == INF) cout << -1 << '\n';
  145.     else cout << best << '\n';
  146.  
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/aMp8T2
language:
C++14 (gcc 8.3)
created:
10 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!