sango【宋壬初吧】

宋壬初吧关注：25贴子：419

1回复贴，共1页

sango

221.194.73.*

var
  i,j,k,w,tt,vv,n,m,x,y,p,t1,t2:longint;
  r:array[0..400,0..400]of longint;
  father:array[0..400]of longint;
  v:array[0..6000]of boolean;
  t:array[0..6000,0..50]of boolean;
  c:array[0..6000,0..3]of longint;
  f:array[0..60]of longint;
procedure sort(l,r:longint);
  var
    i,j,x,tt:longint;
  begin
    i:=l;
    j:=r;
    x:=c[(i+j)div 2,0];
    repeat
      while (c[i,0]<x) do
        i:=i+1;
      while (c[j,0]>x) do
        j:=j-1;
      if (i<=j) then
        begin
          tt:=c[i,0];
          c[i,0]:=c[j,0];
          c[j,0]:=tt;
          tt:=c[i,1];
          c[i,1]:=c[j,1];
          c[j,1]:=tt;
          tt:=c[i,2];
          c[i,2]:=c[j,2];
          c[j,2]:=tt;
          i:=i+1;
          j:=j-1;
        end;
    until (i>j);
    if (l<j) then sort(l,j);
    if (i<r) then sort(i,r);
  end;
function getfather(i:longint):longint;
  begin
    if (father[i]=i) then exit(i);
    father[i]:=getfather(father[i]);
    exit(father[i]);
  end;
function cost(b,e:longint):longint;
  var
    i,j,now,k:longint;
  begin
    cost:=0;
    fillchar(v,sizeof(v),false);
    for i:=1 to n do
      father[i]:=i;
    for i:=1 to m do
      for j:=b to e do
        if (t[i,j]) then
          v[i]:=true;

1楼2009-10-28 16:54回复

221.194.73.*

    for now:=1 to m do
      if (v[now]=false) then
        begin
          i:=getfather(c[now,1]);
          j:=getfather(c[now,2]);
          if (i<>j) then
             begin
               cost:=cost+c[now,0];
               father[i]:=j;
             end;
        end;
    k:=getfather(1);
    for i:=1 to n do
      if (getfather(i)<>k) then
          exit(maxlongint);
    exit(cost);
  end;
begin
  assign(input,'sango.in');reset(input);
  assign(output,'sango.out');rewrite(output);
  read(n,m,tt,vv,w);
  for i:=1 to m do
    begin
      read(c[i,1],c[i,2],c[i,0]);
      c[i,0]:=c[i,0]*vv;
    end;
  sort(1,m);
  for i:=1 to m do
    begin
      r[c[i,1],c[i,2]]:=i;
      r[c[i,2],c[i,1]]:=i;
    end;
  read(p);
  for i:=1 to p do
    begin
      read(x,y,t1,t2);
      k:=r[x,y];
      for j:=t1 to t2 do
        t[k,j]:=true;
    end;
  for i:=1 to tt do
    f[i]:=maxlongint;
  f[0]:=0;
  for i:=1 to tt do
    for j:=0 to i-1 do
      begin
        k:=cost(j+1,i);
        if (k<>maxlongint) then
          x:=f[j]+k*(i-j)+w;
        if (k<>maxlongint)and(x<f[i])
          then f[i]:=x;
      end;
  writeln(f[tt]);
  close(input);close(output);
end.

2楼2009-10-28 16:54

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

1回复贴，共1页

<返回宋壬初吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴

日	一	二	三	四	五	六

sango

登录百度账号

扫二维码下载贴吧客户端