TYPE

link = ^node;

node = RECORD

kk, len: LONGINT;

next: link;

END;

VAR

ed: ARRAY[1..1000000] OF link;

a, b: ARRAY[1..1000, 1..1000] OF LONGINT;

n, m: LONGINT;

num, pr, dist: ARRAY[1..1000000] OF LONGINT;

PROCEDURE init;

VAR

i, j: LONGINT;

p: link;

BEGIN

READ(n);

FOR i:=1 TO n DO

FOR j:=1 TO i DO

READ(a[i, j]);

b[1, 1] := 1;

FOR i:=2 TO n DO BEGIN

b[i, 1] := b[i - 1, i - 1] + 1;

FOR j:=2 TO i DO BEGIN

b[i, j] := b[i, j - 1] + 1;

ed[b[i, j]] := NIL;

END;

END;

FOR i:=2 TO n DO

FOR j:=1 TO i DO BEGIN

IF j > 1 THEN BEGIN

NEW(p);

p^.kk := b[i, j - 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

NEW(p);

p^.kk := b[i - 1, j - 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

END;

IF j < i THEN BEGIN

NEW(p);

p^.kk := b[i, j + 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

NEW(p);

p^.kk := b[i - 1, j + 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

END;

IF j = 1 THEN BEGIN

NEW(p);

p^.kk := b[i, i];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

NEW(p);

p^.kk := b[i - 1, i - 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

END;

IF j = i THEN BEGIN

NEW(p);

p^.kk := b[i, 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

NEW(p);

p^.kk := b[i - 1, 1];

p^.len := a[i, j];

p^.next := ed[b[i, j]];

ed[b[i, j]] := p;

END;

END;

m := b[n, 1];

n := b[n, n];

END;

PROCEDURE swap(ii, jj: LONGINT);

VAR

t: LONGINT;

BEGIN

pr[num[ii]] := jj;

pr[num[jj]] := ii;

t := num[ii]; num[ii] := num[jj]; num[jj] := t;

END;

PROCEDURE heap1(ii: LONGINT);

VAR

x: LONGINT;

BEGIN

x := ii DIV 2;

WHILE x > 0 DO BEGIN

IF dist[num[x]] > dist[num[ii]] THEN swap(ii, x) ELSE EXIT;

ii := x; x := ii DIV 2;

END;

END;

PROCEDURE heap2(ii, x: LONGINT);

VAR

lc, d0, d1, d2: LONGINT;

BEGIN

lc := ii + ii;

IF lc > x THEN EXIT;

d0 := dist[num[ii]];

d1 := dist[num[lc]];

IF lc = x THEN BEGIN

IF d0 > d1 THEN swap(ii, lc);

EXIT;

END;

d2 := dist[num[lc + 1]];

IF d1 < d2 THEN BEGIN

swap(ii, lc);

heap2(lc, x);

END ELSE BEGIN

swap(ii, lc + 1);

heap2(lc + 1, x);

END;

END;

PROCEDURE del0(x: LONGINT);

BEGIN

swap(1, x);

pr[num[x]] := -1;

heap2(1, x - 1);

END;

PROCEDURE xxx;

VAR

i, n0: LONGINT;

p: link;

BEGIN

FOR i:=1 TO n DO BEGIN

pr[i] := i;

num[i] := i;

dist[i] := 999999999;

END;

p := ed[m]; dist[m] := 0;

WHILE p NIL DO BEGIN

dist[p^.kk] := p^.len;

p := p^.next;

END;

FOR i:=n DIV 2 DOWNTO 1 DO heap2(i, n);

del0(n);

FOR i:=1 TO n - 2 DO BEGIN

n0 := num[1];

del0(n - i);

p := ed[n0];

WHILE p NIL DO BEGIN

IF pr[p^.kk] = -1 THEN BEGIN

p := p^.next;

CONTINUE;

END;

IF dist[n0] + p^.len < dist[p^.kk] THEN BEGIN

dist[p^.kk] := dist[n0] + p^.len;

heap1(pr[p^.kk]);

END;

p := p^.next;

END;

END;

END;

BEGIN

init;

xxx;

WRITELN(dist[1] + a[1, 1]);

END.

Dijkstra+堆优化的。

只过了6，10两个点。