fork download 
  1. var
  2.   f,d:array[0..1000]of longint;
  3.   v:array[1..1000]of boolean;
  4.   i,j,k,n,m,e,x,y,t,p,w:longint;
  5.   c:array[1..100,0..100]of longint;
  6.   a:array[1..100,1..100]of longint;
  7.  
  8. function dji(x,y:longint):longint;
  9. var i,j,k,min:longint;
  10. begin
  11.   fillchar(d,sizeof(d),$7f);
  12.   fillchar(v,sizeof(v),0);
  13.   d[1]:=0;
  14.   for i:=x to y do
  15.     for j:=1 to c[i,0] do
  16.       v[c[i,j]]:=true;
  17.   for i:=1 to m do
  18.   begin
  19.     min:=10000000;k:=0;
  20.     for j:=1 to m do
  21.       if not v[j] and(d[j]<min) then begin min:=d[j];k:=j;end;
  22.     if (k=0)or(k=m) then break;
  23.     v[k]:=true;
  24.     for j:=1 to m do
  25.       if not v[j] and(d[j]>a[k,j]+d[k]) then d[j]:=a[k,j]+d[k];
  26.   end;
  27.   exit(d[m]);
  28. end;
  29. begin
  30.   readln(n,m,k,e);
  31.   fillchar(a,sizeof(a),$7f);
  32.   for i:=1 to e do
  33.   begin
  34.     read(x,y);
  35.     readln(a[x,y]);
  36.     a[y,x]:=a[x,y];
  37.   end;
  38.   readln(t);
  39.   for i:=1 to t do
  40.   begin
  41.     readln(p,x,y);
  42.     for j:=x to y do
  43.     begin
  44.       inc(c[j,0]);
  45.       c[j,c[j,0]]:=p;
  46.     end;
  47.   end;
  48.   for i:=1 to n do
  49.   begin
  50.     f[i]:=maxlongint;
  51.     for j:=1 to i do
  52.     begin
  53.       w:=dji(j,i);
  54.       if w>10000000 then continue;
  55.       if f[i]>k+f[j-1]+w*(i-j+1) then f[i]:=k+f[j-1]+w*(i-j+1);
  56.     end;
  57.   end;
  58.   writeln(f[n]-k)
  59. end.
Success #stdin #stdout 0s 320KB
comments (?)
stdin 
5 5 10 8

1 2 1

1 3 3

1 4 2

2 3 2

2 4 4

3 4 1

3 5 2

4 5 2

4

2 2 3

3 1 1             

3 3 3

4 4 5
stdout 
32
https://ideone.com/48NJNh
language:
Pascal (fpc 3.0.4)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!