Farmer John מחפש בסירה אוצר אגדי באחד מ־$N$ איי $(1 \le N \le 100)$ Cowribbean Sea, ממוספרים $1,\ldots,N$.
המפה דורשת להתחיל ב־1 ולסיים ב־$N$ דרך $A_{1}$, $A_{2}$, ..., $A_{M}$, סדרת $M$ איים $(2 \le M \le 10,000)$, לפני הופעת האוצר. אפשר לבקר בהם ובאחרים שלא בסדר ושוב, אך המסע חייב לכלול $A_{i}$ לפי המפה.
FJ רוצה להימנע משודדי ים ויודע סכנה $(0 \le danger \le 100,000)$ בין כל זוג. הסך הוא סכום סכנות כל הדרכים שבהן עובר.
מצאו את המסלול הפחות מסוכן לאוצר העומד במפה.
קלט
- שורה1: שני שלמים ברווח, $N$ ו־$M$.
- שורות $2,\ldots,M+1$: שורה $i+1$ מתארת את האי החובה ה־$i_{th}$ בשלם $A_{i}$.
- שורות $M+2,\ldots,N+M+1$: שורה $i+M+1$ מכילה $N$ שלמים ברווח לסכנות מ־$i$ ל־1, 2, ..., $N$. ה־$i$ תמיד אפס.
פלט
- שורה1: סכנה מזערית להשגת האוצר.
דוגמאות
קלט 1
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
פלט 1
7
הערה
3 איים ו4 ביקורים:1, 2, שוב1, לבסוף3. דרכים(1,2), (2,3), (3,1) והפוכות מסוכנות5, 2, 1.
מסלול1, 3, 2, 3, 1, 3 נותן7 וכולל1, 2, 1, 3. נמנעים מ־1–2 המסוכן.
מחבר הבעיה: Jeffrey Wang, 2007