시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 8 | 4 | 3 | 42.857% |
Consider a town whose road network forms an $N * M$ grid, where adjacent intersections are connected by roads. All roads are bi-directional. Each direction has an associated number - the time needed to travel from one end-point to another.
Each direction of each road consists of one or more lanes. A lane can serve one of the following functions: left-turn, straight, right-turn, or any combination of them. However, a left-turn lane cannot be placed to the right of a straight or right-turn lane, and a straight lane cannot be placed to the right of a right-turn lane. There are no U-turn lanes.
The rules for crossing intersections are illustrated in the above figure (suppose a car enters the intersection from the south). To make a left turn, it must be in one of the $L$ left-turn lanes; let's number them $1$ through $L$ from left to right. The traffic rule says Lane $i$ must turn into the $i$-th lane (counting from the left) of the target road, except that Lane $L$ may turn into the $L$-th lane or any other lanes to its right.
Similarly, to go straight through an intersection, the car must be in one of the $S$ straight lanes; let's number them $1$ through $S$ from left to right. Lane $i$ must go into the $i$-th lane (counting from the left) of the target road, except that Lane $S$ may go into the $S$-th lane or any other lanes to its right.
To make a right turn, the car must be in one of the $R$ right-turn lanes. For the convenience of discussion, we consider these lanes and those of the target road from right to left. Let's number the right-turn lanes $1$ through $R$ from right to left. Lane $i$ must turn into the $i$-th lane (counting from the right) of the target road, except that Lane $R$ may turn into the $R$-th lane or any other lanes to its left.
It is guaranteed that if at least one left-turn / straight / right-turn lane is present, the target road must exist and have enough lanes to accommodate the left turn / straight / right turn, respectively. The time spent on crossing intersections is negligible.
In addition, a driver may change lanes in the middle of a road. Note that in the above rules for intersections, it doesn't count as a lane change to drive into any of the legal lanes of the target road. The time spent on lane changes is negligible.
A trip starts and ends at the rightmost lane of the midpoint of roads. The time needed to travel midpoint-to-endpoint is half of endpoint-to-endpoint.
You are running a taxi company called "Safest Taxi" in this town, with the slogan "your safety is in your hands". You let your customers choose the numbers $X$ and $Y$ for their trip, and the driver will make at most $X$ left turns and $Y$ lane changes to accomplish the trip.
What is the shortest time to fulfill each trip given the rules?
The first line consists of three integers $N$ ($2 \leq N \leq 15$), $M$ ($2 \leq M \leq 15$) and $K$ ($1 \leq K \leq 3$), separated by a single space. The town's road network has $N$ intersections north-south and $M$ intersections west-east. Each road has $K$ lanes.
The second line consists of a single integer $D$. The town's road network has $D$ road segments. Every adjacent pair of intersections must appear in the list exactly once.
Each of the next $D$ lines describes a road segment with the following format:
$$R_0\;C_0\;R_1\;C_1\;T\;L_0\;L_1 ... L_{K-1}$$
This describes a road segment going from the intersection at row $R_0$ column $C_0$ to the intersection at row $R_1$ column $C_1$ ($0 \leq R_0,R_1<N$, $0 \leq C_0,C_1<M$). Rows are numbered $0$ through $N-1$ from north to south, and columns are numbered $0$ through $M-1$ from west to east. The segment must connect two adjacent intersections, i.e., $\mid R_0 - R_1 \mid + \mid C_0 - C_1\mid = 1$. The time to travel through the entire segment is $T$ ($2 \leq T \leq 100$, $T$ must be an even number). The next $K$ strings describe the function of each of the $K$ lanes, from left to right, with the following semantics:
The next line consists of a single integer $P$ ($1 \leq P \leq 50$), the number of trips to fulfill.
Each of the next $P$ lines describes a trip with the following format:
$$R_{S0}\;C_{S0}\;R_{S1}\;C_{S1}\;R_{D0}\;C_{D0}\;R_{D1}\;C_{D1}\;X\;Y$$
This indicates that the starting point is the midpoint of segment ($R_{S0}, C_{S0}$) $\to$ ($R_{S1}, C_{S1}$), and the destination is the midpoint of segment ($R_{D0}, C_{D0}$) $\to$ ($R_{D1}, C_{D1}$). Both segments must appear in the above list. Both the starting point and the destination are on the rightmost lane. The customer requests that at most $X$ ($0 \leq X \leq 4$) left turns and $Y$ ($0 \leq Y \leq 4$) lane changes are allowed for the trip.
Output $P$ lines. The $i$-th line contains a single integer which is the shortest time to fulfill each trip given the rules, or $-1$ if no feasible route exists.
3 3 2 24 0 0 0 1 6 S R 0 1 0 0 8 L L 0 1 0 2 16 R R 0 2 0 1 18 LS S 0 0 1 0 8 LS S 1 0 0 0 8 R R 0 1 1 1 10 LS SR 1 1 0 1 16 L R 0 2 1 2 8 S R 1 2 0 2 8 L L 1 0 1 1 6 L SR 1 1 1 0 8 L R 1 1 1 2 16 L R 1 2 1 1 18 L SR 1 0 2 0 8 L L 2 0 1 0 8 S R 1 1 2 1 10 L R 2 1 1 1 8 LS SR 1 2 2 2 8 R R 2 2 1 2 8 LS S 2 0 2 1 10 LS S 2 1 2 0 12 R R 2 1 2 2 6 L L 2 2 2 1 8 S SR 6 2 1 1 1 1 1 1 0 1 1 2 1 1 1 1 1 1 0 1 0 2 1 1 1 1 1 1 0 0 0 0 1 0 2 0 2 0 1 2 0 1 0 0 0 0 0 1 0 2 0 2 1 2 0 2 0 2 1 2 0
8 48 66 131 112 95
The first three lines of the sample output are illustrated in the figure below.
ICPC > Regionals > North America > North Central North America Regional > NCNA 2020 G번
ICPC > Regionals > North America > Southern California Regional > 2020 Southern California Regional 11번