일방통행

문제

1 에서 출발하여 N 까지 최소 길찾기, 길은 일방통행 임

각 노드는 빨걍, 파랑, 그린, 흰색을 가지는데

노드의 색깔이 

빨강색이면 빨강색 통행증 제출 (빨강색 통행증이 없으면 나갈 수 없음)

파랑색이면 파랑색 통행증 제출 (파랑색 통행증이 없으면 나갈 수 없음)

그린이면 그대로 통과

흰색이면 통행증 지급, 단 통행증은 각각 1개를 초과할 수 없다.

출발시 빨간 통행증랑1 파란 통행증 1을 가지지고 출발한다.

1에서 N까지 최소 길을 찾는 문제

---

입력

테스트 개수

노드의 수 1<=N<100,000

간선의 수 1<=M<300,000

색깔이 문자열로 주어짐

M개의 간선과 길이가 주어짐

---

출력

#+test_case + 1에서 출발하여 N 에 도착하는 최소 비용을 출력

만약 도달할 수 없다면 -1 출력

---

힌트

입력 예제

3

RBRGWBR

7 9 

1 2 1

2 3 4

3 2 3

2 4 5

4 3 7

2 5 3

5 1 10

4 6 2

6 7 3

5 8

RBWGGB

1 2 2

1 3 3

1 4 1

1 5 10

2 4 2

3 4 1

3 5 1

4 5 3

5 5

RBWGR

1 2 1

2 3 6

3 2 5

2 4 3

4 5 2

#include <iostream> #include <queue> #include <vector> struct PATH{ int X; //시작점 int Y; //도착지 long long P; //비용 } char Node[100001]; //지점별 색깔 vector<path> PathV[300001]; //DP 저장용도, 어떤 지점에서 파랑색, 빨강색 통행권 개수에 따라 갈 수 있는 최소 금액 //[지점][파랑][빨강], -1로 초기화(방문 안함) long long P[100001][2][2] strcut PASSPORT{ int X; //지점 int Blue; //파랑색 통행권 개수 int Red; //빨강색 통행권 개수 long long P; //현재까지 든 비용 } int main(){ //Node 입력받음 //PathV 입력받음 PASSPORT startPassport = {1,1,1,0}; queue<passport> visitQ; while(!visitQ.emptry()){ PASSPORT curPassport = visitQ.front(); visitQ.pop(); vector<path>::iterator iter; //연결된 지점 확인 for(iter = PathV[curPassport.X].begin(); iter != PathV[curPassport.X].end(); iter++){ PATH nextPath = (*iter); curBlue = curPassport.Blue; curRED = curPassport.Red; nextBlue = curPassport.Blue; nextBlue = curPassport.Red; if(Node[nextPath.X]=='W'){ nextBlue = 1; nextRed = 1; }else if(Node[nextPath.X]=='B'){ if(curBlue==0){ continue; //통행권이 없어서 갈 수 없음 }else{ nextBlue = 0; } }else if(Node[nextPath.X]=='R'){ if(curRed==0){ continue; //통행권이 없어서 갈 수 없음 }else{ nextRed = 0; } } //처음 방문이거나 현재 가는 곳이 비용이 더 적게 들 경우에 큐에 넣어줌 if(P[nextPath.Y][nextBlue][nextRed] == -1 || curPassport.P + nextPath.P < P[nextPath.Y][nextBlue][nextRed]){ PASSPORT nextPassport = {nextPath.Y,nextBlue,nextRed, curPassport.P + nextPath.P}; visitQ.push(nextPassport); P[nextPath.Y][nextBlue][nextRed] = curPassport.P + nextPath.P; } } } //마지막 노드에서 최소 금액 출력함 }