SSSP

[T0peerakarn]

Statement

มีสายกีตาร์ N สาย เรียงลำดับจากซ้ายไปขวาตั้งแต่สายที่ 1, 2, 3, ..., N
กำหนด Metric p ขนาด N * N โดยที่ p[i][j] แทนแรงที่ใช้ในการเคลื่อนมือจากสายที่ i ไปสายที่ j

การเคลื่อนมือจากสาย i ไปสาย j ไม่สามารถแวะกลางทางได้ กล่าวคือหากมีสาย k ที่ทำให้ a[i][k] + a[k][j] < a[i][j]
การเคลื่อนมือจากสาย i ไปสาย j ก็ต้องใช้แรง a[i][j] เท่านั้น

ต้องการจะเล่นเพลง ๆ หนึ่ง โดยที่เพลงนั้นจะเกิดจากการดีดสายกีตาร์ตามลำดับ กำหนดให้การดีดสายใด ๆ ไม่เสียแรง
ลำดับเพลงที่จะเล่นแทนด้วย S มีความยาว M จะได้ว่า 1 <= S_i <= N, for i in [1, M]

สามารถเลือกที่จะไม่เล่นเพลงได้ไม่เกิน K จุด เช่น
ให้ sequence เป็น 3 2 3 5 7 4, แรงที่ใช้จะเป็น p[3][2] + p[2][3] + p[3][5] + p[5][7] + p[7][4]
หากเลือกที่จะไม่เล่น S_5, แรงที่จะใช้จะเป็น p[3][2] + p[2][3] + p[3][5] + p[5][4]
หากเลือกที่จะไม่เล่น S_5 และ S_6, แรงที่จะใช้จะเป็น p[3][2] + p[2][3] + p[3][5]

ตอนเริ่มต้นสามารถวางมือที่สายใดก็ได้โดยที่ไม่เสียแรง
จงหาแรงที่น้อยที่สุดที่ใช้เล่นเพลงโดยที่ข้ามได้ไม่เกิน K จุด

Concept

มอง S_i ใด ๆ เป็น node แล้วสร้าง directed edge เชื่อม S_i -> S_j, for 1 <= i < j <= M
graph ที่ได้จะเปลี่ยนเป็นปัญหา SSSP เก็บ state

[T0peerakarn]

Subtask

• k = 0
• k = 1
• N, M, K <= 20 (bruteforce on sequence)
• N, M, K <= 300 (dp)