מחיר מינימלי במסלול רכבת

במסלול של רכבת n ישנן תחנות. מחירי הכרטיסים של הנסיעות מתחנה i לתחנה j כאשר j גדול ממש מ-i (נתונים במערך דו-ממדי).

לדוגמה, מערך המחירים של הכרטיסים הוא זה:

שימו לב, הערכים בתאים במיקום בהם i גדול מ- j  הם 1-, כי מותר לנסוע רק בכיוון אחד (רק מ-i ל-j שמקיימים i<j, וכאשר הם שווים, המחיר הוא 0, כי נשארים בתחנה).

 0123
00158090
1-104050
2-1-1070
3-1-1-10

בדוגמה לעיל, המחיר המינימלי הוא 65, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

יש להחזיר את המחיר המינימלי של של נסיעה מהתחנה הראשונה 0 לאחרונה n-1.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:
  • המערך תקין, וערכי כל התאים באלכסון הראשי הם 0 ומתחת לאלכסון הראשי הם -1.
  • כל הנסיעות מתחנה i לתחנה j אפשריות. אין תאים ריקים.
  • מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי.
  • אסור להשתמש במשתנים גלובליים (סטטיים)!
דוגמה 1:
קלט: 
mat =
[[0, 15, 80, 90],
 [-1, 0, 40, 50],
 [-1, -1, 0, 70],
 [-1, -1, -1, 0]]
פלט: 
65

הסבר: המחיר המינימלי הוא 65, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

דוגמה 2:
קלט: 
mat =
[[0, 10, 75, 94],
 [-1, 0, 35, 50],
 [-1, -1, 0, 60],
 [-1, -1, -1, 0]]
פלט: 
60

הסבר: המחיר המינימלי הוא 60, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 2 ומתחנה 2 לתחנה 3.

דוגמה 3:
קלט: 
mat =
[[0, 20, 50, 70],
 [-1, 0, 30, 40],
 [-1, -1, 0, 60],
 [-1, -1, -1, 0]]
פלט: 
60

הסבר: המחיר המינימלי הוא 60, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

דוגמה 4:
קלט: 
mat =
[[0, 5, 20, 30],
 [-1, 0, 15, 25],
 [-1, -1, 0, 10],
 [-1, -1, -1, 0]]
פלט: 
30

הסבר: המחיר המינימלי הוא 30, אפשר להגיע אליו אם נוסעים ישירות מתחנה 0 לתחנה 3.

דוגמה 5:
קלט: 
mat =
[[0, 8, 50, 60],
 [-1, 0, 20, 30],
 [-1, -1, 0, 40],
 [-1, -1, -1, 0]]
פלט: 
38

הסבר: המחיר המינימלי הוא 38, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

דוגמה 6:
קלט: 
mat =
[[0, 12, 60, 80],
 [-1, 0, 25, 35],
 [-1, -1, 0, 45],
 [-1, -1, -1, 0]]
פלט: 
47

הסבר: המחיר המינימלי הוא 47, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

דוגמה 7:
קלט: 
mat =
[[0, 7, 30, 50],
 [-1, 0, 18, 28],
 [-1, -1, 0, 38],
 [-1, -1, -1, 0]]
פלט: 
35

הסבר: המחיר המינימלי הוא 35, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

דוגמה 8:
קלט: 
mat =
[[0, 9, 40, 70],
 [-1, 0, 22, 32],
 [-1, -1, 0, 42],
 [-1, -1, -1, 0]]
פלט: 
41

הסבר: המחיר המינימלי הוא 41, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

Loading...
נשמרLn 1, Col 1

קלט:

mat =
[[0, 15, 80, 90],
 [-1, 0, 40, 50],
 [-1, -1, 0, 70],
 [-1, -1, -1, 0]]

הפלט המבוקש:

65