CSES - Flight Discount | Khuyến mãi chuyến bay
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Metsälä.
- Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Mỗi chuyến bay đều là một chiều.
- Bạn có thể giả định rằng luôn luôn có thể đi từ Syrjälä đến Metsälä.
Output
- In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
- Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là \(x\), giá tiền của nó trở thành \(\lfloor x/2 \rfloor\) (làm tròn xuống một số nguyên).
Constraints
- \(2 \le n \le 10^5\)
- \(1 \le m \le 2 \cdot 10^5\)
- \(1 \le a,b \le n\)
- \(1 \le c \le 10^9\)
Example
Sample input
3 4
1 2 3
2 3 1
1 3 7
2 1 5
Sample output
2
Bình luận
ý tưởng quy hoạch động : gọi dp[i][j] chi phí nhỏ nhất để đi đến đỉnh v
và đã dùng vé (với j = 0 : chưa dùng vé , j = 1 : đã dùng vé)
ta có công thức :
TH1 dùng vé : với j = 0 ta có d[v][1] > d[u][j] + w/2 => d[v][1] = d[u][j] + w/2
TH2 không dùng vé : ta có d[v][j] > d[u][j] + w => d[v][j] = d[u][j] + w
code mẫu theo hướng quy hoạch cho bạn nào cần tham khảo : https://ideone.com/d8HE5U
-
0
truongngoclamCB1
4:53 p.m. 22 Tháng 8, 2024
1 bình luận nữacái này dùng dijkstra rồi tìm cái lớn nhất chia 2 ra không được hả bạn?