Chào mừng bạn đến với Selfomy Hỏi Đáp, hãy Hỏi bài tập hoặc Tham gia ngay
0 phiếu
393 lượt xem
trong Tin học lớp 11 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)

Tờ báo CTT (Chuyên Toán-Tin) phát hành với số lượng lớn trên N tỉnh 1..N, N chẵn và N£1000 do đó phải in tại hai nhà in đặt ở tỉnh 1 và tỉnh 2. Hàng ngày từ mỗi nhà in có N/2 ô tô chở báo đến N tỉnh, mỗi ô tô chở báo đi một tỉnh, hai ô tô khác nhau chở báo đi hai tỉnh khác nhau, giữa hai tỉnh khác nhau có không quá một đoạn đường nối trực tiếp và không có hai đoạn đường nào cắt nhau. Các xe khi đi từ nhà in đến bất kỳ tỉnh nào cũng đều biết cách đi theo đường ngắn nhất.

Hãy tìm cách phân phối báo từ các nhà in đến các tỉnh sao cho tổng độ dài đường đi của các ô tô là nhỏ nhất.

Dữ liệu vào được cho bởi file CTT.INP trong đó dòng thứ nhất ghi hai số N, M, tiếp theo là M dòng, mỗi dòng ghi ba số nguyên dương X, Y, L có nghĩa là có đoạn đường nối trực tiếp hai tỉnh X, Y với độ dài L, L không lớn hơn 1000. Luôn có ít nhất một cách chuyển báo đến tất cả N tỉnh. Độ dài đường đi từ nhà in tại tỉnh nào đến chính tỉnh đó xem như bằng 0.

Kết quả ghi ra file CTT.OUT hai dòng, dòng thứ nhất ghi tên các tỉnh nhận báo từ nhà in tại tỉnh 1, dòng thứ hai ghi tên các tỉnh nhận báo từ nhà in tại tỉnh 2.

Ví dụ:

CTT.INP

CTT.OUT

6 8

1 2 5

1 4 8

1 6 7

2 3 6

3 4 5

3 6 2

4 5 3

5 6 2

1 4 5

2 3 6

 

 


1 Câu trả lời

0 phiếu
bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
 
Hay nhất
const
  INP = 'CTT.INP';
  OUT = 'CTT.OUT';
  MaxN = 1000;
  Infinity =1000000000;

type
  PNode = ^TNode;
  TNode = record
            v, w : Integer;
            Next : PNode;
          end;
  TDist = array[1..MaxN] of LongInt;

var
  List : array[1..MaxN] of PNode;
  Dist1, Dist2 : TDist;
  Chon : array[1..MaxN] of Byte;
  N : Integer;
  f : Text;
  Result : LongInt;

procedure Add(u, v, w : Integer);
var
  tmp : PNode;
begin
  New(tmp);
  tmp^.v:=v; tmp^.w:=w;
  tmp^.Next:=List[u];
  List[u]:=tmp;
end;

procedure Init;
var
  i, u, v, w : Integer;
  M : LongInt;
begin
  Assign(f, INP); Reset(f);
  Readln(f, N, M);
  for i:=1 to N do
    List[i]:=nil;
  for i:=1 to M do
    begin
      Readln(f, u, v, w);
      Add(u, v, w);
      Add(v, u, w);
    end;
  Close(f);
end;

procedure Dijkstra(Start : Integer; var Dist : TDist);
var
  Heap, Pos : array[1..MaxN] of Integer;
  Chua : array[1..MaxN] of Boolean;
  Last, i : Integer;
  HeapSize : Integer;
  tmp : PNode;

  procedure UpHeap(i : Integer);
  var
    x, c, r : Integer;
  begin
    x:=Heap[i];
    c:=i; r:=i shr 1;
    while r > 0 do
      begin
        if Dist[Heap[r]] > Dist[x] then
          begin
            Heap[c]:=Heap[r];
            Pos[Heap[r]]:=c;
          end
        else
          Break;
        c:=r; r:=r shr 1;
      end;
    Heap[c]:=x;
    Pos[x]:=c;
  end;

  procedure DownHeap(i : Integer);
  var
    x, c, r : Integer;
  begin
    x:=Heap[i];
    c:=i; r:=i shl 1;
    while r <= HeapSize do
      begin
        if (r < HeapSize) and (Dist[Heap[r]] > Dist[Heap[r+1]]) then
          Inc(r);
        if Dist[Heap[r]] < Dist[x] then
          begin
            Heap[c]:=Heap[r];
            Pos[Heap[r]]:=c;
          end
        else
          Break;
        c:=r; r:=r shl 1;
      end;
    Heap[c]:=x;
    Pos[x]:=c;
  end;

  function Extract : Integer;
  begin
    Extract:=Heap[1];
    Heap[1]:=Heap[HeapSize];
    Pos[Heap[HeapSize]]:=1;
    Dec(HeapSize);
    DownHeap(1);
  end;

begin
  FillChar(Chua, Sizeof(Chua), True);
  for i:=1 to N do
    Dist[i]:=Infinity;
  Chua[Start]:=False;
  Dist[Start]:=0;
  HeapSize:=0;
  for i:=1 to N do
    if i <> Start then
      begin
        Inc(HeapSize);
        Heap[HeapSize]:=i;
        Pos[i]:=HeapSize;
      end;
  Last:=Start;
  for i:=2 to N do
    begin
      tmp:=List[Last];
      while tmp <> nil do
        begin
          if Chua[tmp^.v] and (Dist[Last] + tmp^.w < Dist[tmp^.v]) then
            begin
              Dist[tmp^.v]:=Dist[Last] + tmp^.w;
              UpHeap(Pos[tmp^.v]);
            end;
          tmp:=tmp^.Next;
        end;
      Last:=Extract;
    end;
end;

procedure Process;
var
  Sub : array[1..MaxN] of LongInt;
  cs : array[1..MaxN] of Integer;
  i : Integer;

  procedure QuickSort(l, r : Integer);
  var
    x : LongInt;
    i, j, tmp : Integer;
  begin
    if l >= r then Exit;
    x:=Sub[cs[Random(r-l+1)+l]];
    i:=l; j:=r;
    repeat
      while (i < r) and (Sub[cs[i]] < x) do Inc(i);
      while (j > l) and (Sub[cs[j]] > x) do Dec(j);
      if i <= j then
        begin
          if i < j then
            begin
              tmp:=cs[i];
              cs[i]:=cs[j];
              cs[j]:=tmp;
            end;
          Inc(i); Dec(j);
        end;
    until i > j;
    QuickSort(l, j); QuickSort(i, r);
  end;

begin
  Dijkstra(1, Dist1);
  Dijkstra(2, Dist2);
  for i:=1 to N do
    begin
      cs[i]:=i;
      Sub[i]:=Dist1[i] - Dist2[i];
    end;
  QuickSort(1, N);
  Result:=0;
  for i:=1 to N div 2 do
    begin
      Chon[cs[i]]:=1;
      Inc(Result, Dist1[cs[i]]);
    end;
  for i:=N div 2 + 1 to N do
    begin
      Chon[cs[i]]:=2;
      Inc(Result, Dist2[cs[i]]);
    end;
  Writeln('Result : ', Result);
end;

procedure Done;
var
  i : Integer;
begin
  Assign(f, OUT); Rewrite(f);
  for i:=1 to N do
    if Chon[i] = 1 then
      Write(f, i, ' ');
  Writeln(f);
  for i:=1 to N do
    if Chon[i] = 2 then
      Write(f, i, ' ');
  Close(f);
end;

BEGIN
  Init;
  Process;
  Done;
END.

Các câu hỏi liên quan

0 phiếu
0 câu trả lời 397 lượt xem
Cho n đoạn trên trục số, đoạn thứ i là [Li, Ri]. Hãy chọn ra trong các đoạn kể trên một số ít nhất các đoạn để phủ hết đoạn [a, b] Dữ ... 4 7 10 9 11 8 11 3 1 4 6 8 1 200 1 4 2 5 4 5 6 45 6 7 5 7 100 200 50 99 -1
đã hỏi 3 tháng 1, 2021 trong Tin học lớp 11 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
+2 phiếu
0 câu trả lời 451 lượt xem
Trong truyện cổ tích "Cây Khế" ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu báu ... ;c chọn. Ví dụ: CAYKHE.INP CAYKHE.OUT 5 10 20 3 19 1 30 7 24 3 15 6 63 3 1 2 4
đã hỏi 11 tháng 1, 2021 trong Tin học lớp 11 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 332 lượt xem
An được mời tham gia trò chơi "Siêu thị may mắn" do đài truyền hình ZTV tổ chức. Siêu thi được đặt trong trường quay truyền hình có n ... ;c trong cách mua này. Ví dụ: SMARKET.INP SMARKET.OUT 12 3 4 1 6 2 2 1 2 0 2 0
đã hỏi 8 tháng 1, 2021 trong Tin học lớp 11 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 630 lượt xem
Có N người xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. ... qui ước ghi số 0) Ví dụ TICK.INP TICK.OUT 5 2 5 7 8 4 3 9 10 10 17 2 4
đã hỏi 2 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
0 câu trả lời 261 lượt xem
Tìm n>1, n là số nguyên tố sao cho 2^n+n^2 là số nguyên tố.  
đã hỏi 17 tháng 1, 2021 trong Toán lớp 8 bởi phuphuphu Cử nhân (1.7k điểm)
+1 thích
1 trả lời 507 lượt xem
Trên hai đường thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đường thẳng L1 được đánh ... ; tăng dần. Ví dụ: WIRES.INP WIRES.OUT 9 2 5 3 8 7 4 6 9 1 5 2 3 4 6 9
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 130 lượt xem
Một người sử dụng INTERNET đặt yêu cầu nhận thông tin về một số chủ đề khác nhau từ một số địa chỉ truy nhập. Chủ của các ... ;t nhất cần thực hiện. Ví dụ: EMAIL.INP EMAIL.OUT 7 1 3 4 3 2 2 3 4
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
2 câu trả lời 1.6k lượt xem
Hai xe ô tô khởi hành cùng một lúc từ 2 địa điểm A và B. Xe thứ nhất đi quãng đường từ A đến B hết 4h15'. Xe thứ hai đi từ B đến A hết 3h45'. Đến chỗ gặp nhau, xe ô tô thứ hai đi đi quãng đường dài hơn xe ô tô thứ nhất là 20km.  Tính độ dài quãng đường AB.  GIẢI GIÚP MK VS NHA!!! 
đã hỏi 31 tháng 3, 2017 trong Toán lớp 7 bởi Thương Dương Cử nhân (4.1k điểm)
+3 phiếu
2 câu trả lời 1.2k lượt xem
Nói về lòng yêu nước, nhà văn I. Ê-ren-bua có câu nói nổi tiếng: "Dòng suối đổ vào sông, sông đổ vào  trường giang Vôn-ga, con sông Vôn-ga đi ra biển. Lòng yêu nhà, yêu làng xóm, yêu miền quê trở nên lòng yêu tổ quốc." Em hiểu câu nói trên như thế nào? Hãy phát biểu những suy nghĩ của em về quê hương đất nước.  
đã hỏi 26 tháng 1, 2017 trong Ngữ văn lớp 7 bởi Titania Học sinh (387 điểm)
0 phiếu
9 câu trả lời 673 lượt xem
Nghĩ theo ý hiểu
đã hỏi 19 tháng 3, 2017 trong Khác bởi Q_U_Ỳ_N_H - C_U_T_E Thần đồng (841 điểm)

HOT 1 giờ qua

  1. nguyenmanh04102009212

    166 Điểm

  2. tnk11022006452

    120 Điểm

  3. hoconghung031007464

    80 Điểm

Phần thưởng hằng tháng
Hạng 1: 200.000 đồng
Hạng 2: 100.000 đồng
Hạng 3: 50.000 đồng
Hạng 4-10: 20.000 đồng
Bảng xếp hạng cập nhật 30 phút một lần
...