백준 13213 (C++) Binary Roads

최초 업로드: 2025-08-08 13:19:01

최근 수정 시간: 2025-08-08 13:19:33

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] Binary Roads

[문제 링크](https://www.acmicpc.net/problem/13213)

## 문제 설명

Ali is out on a vacation and intends to visit a specific destination. However, he has trouble getting there in the shortest possible time and needs your help!

For simplicity, the place can be treated as a graph with N nodes (places) and E edges (roads). Nodes will be labelled from 0 to N-1 and all edges are bi-directional. It can be assumed that it will take 1 hour to travel any edge and all nodes and edges can be visited more than once.

Ali will start of at node 0 and his destination is node N-1. This seems like an easy problem, but things are much more complicated due to binary roads.

Unlike normal roads, all of the E edges are binary roads. They either contain a value of 0 or 1. Similarly, Ali will also have a value of 0 or 1. When Ali has a value of 0, he can only travel on edges with a value of 0. When Ali has a value of 1, he can only travel on those edges with a value of 1. However, after travelling on a single edge, the value of Ali will be flipped. If it was originally 0, it will become 1. If it was originally 1, it will become 0. It will then flip again after he travels on another edge.

Still, Ali wants to know the shortest possible time to reach his destination (in hours). Remember, Ali can choose to start with value 0 or 1 .

## 입력

The first line of input will contain 2 integers, N and E. (1 ≤ N ≤ 200,000, 0 ≤ E ≤ 1,000,000)

The next E line of input will contain 3 integers: A, B, and V. This means that there is a bi-directional edge from node A to node B with a value of V. It is guaranteed that there will not be more than one edge connecting the same two nodes with the same value.

It is guaranteed that A ≠ B, 0 ≤ A, B < N, V = 0 or 1 for all E lines describing the edges.

## 출력

Output a single integer, the shortest possible time for Ali to reach his destination (in hours). If it is not possible for Ali to reach his destination, output -1 instead.

## 풀이
#### v가 0일 때와 1일 때를 구분하는 bfs 문제이다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> pi;

const int MAX = 200'000;

vvvi conn(2, vvi(MAX));
int cost[2][MAX];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, e; cin >> n >> e;
    while(e--) {
        int a, b, v; cin >> a >> b >> v;
        conn[v][a].push_back(b);
        conn[v][b].push_back(a);
    }

memset(cost, -1, sizeof cost);
 queue<pi> q; q.push({0, 0}); q.push({1, 0}); // {v, pos}
 cost[0][0] = cost[1][0] = 0;
 while(!q.empty()) {
 auto cur = q.front(); q.pop();
 if(cur.second == n-1) {
 cout << cost[cur.first][cur.second];
 return 0;
 }
 for(int next : conn[cur.first][cur.second]) {
 pi nn = {cur.first^1, next};
 if(cost[nn.first][nn.second]==-1) {
 cost[nn.first][nn.second] = cost[cur.first][cur.second]+1;
 q.push(nn);
 }
 }
 }
 cout << -1;
}
```