toi

TOI14 logistics - โลจิสติกส์ (LOGISTICS)

🏠 รวมเฉลย TOI14

💎 problem.pdf

🎉 toi14_logistic.cpp

Shortest Path หลายมิติ ใช้ Dijkstra’s algorithm

dp[เมือง][น้ำมัน][ตั๋วพิเศษ] = ค่าใช้จ่ายถูกสุด (price)

โดยมีเงื่อนไขการเปลี่ยน State ตามนี้

1. เดินทางโดยใช้น้ำมันในถัง dp[new_node][fuel - use_fuel][ticket] = price
2. เติมน้ำมัน 1 หน่วยโดยจ่ายเงิน dp[node][fuel + 1][ticket] = price + cost[node]
3. เติมน้ำมันจนเต็ม โดยจ่ายตั๋ว dp[node][fuel_capacity][0] = dp[node][*][1]