Transport cost

CHIPHI.pas

uses crt, math, sysutils;

type
  node = record
    price, currentPrice, maxPricePassed: longint;
    paths: array of longint;
    visited: boolean;
  end;

  request = record
    st, en: longint;
  end;

var f, logFile: text;
    nodes: array of node; requests: array of request;
    i, numOfNodes, numOfPaths, numOfRequests, tmpNum1, tmpNum2, tmpNum3: longint;

procedure log(text: array of string);
var k: longint;
begin
  for k:=0 to length(text)-1 do begin
    write(logFile, text[k]);
    write(text[k]);
  end;
  writeln(logFile);
  writeln;
end;

function findLowestPrice(st, en: longint): longint;
var j, tmpValue, minNode, current: longint;
begin
  log(['    Initializing...']);
  for j:=1 to numOfNodes-1 do begin
    nodes[j].currentPrice := -1;
    nodes[j].maxPricePassed := nodes[j].price;
    nodes[j].visited := false;
  end;
  current := st;
  nodes[current].currentPrice := nodes[current].price;
  nodes[current].maxPricePassed := nodes[current].price;
  while true do begin
    log(['    Checking node #', intToStr(current+1), ' (price ', intToStr(nodes[current].price), '; current price ', intToStr(nodes[current].currentPrice), '; max price passed ', intToStr(nodes[current].maxPricePassed), ').']);
    for j:=0 to numOfNodes-1 do if nodes[current].paths[j] > -1 then begin
      if not nodes[j].visited then begin
        tmpValue := nodes[current].currentPrice + nodes[current].paths[j];
        if nodes[j].price > nodes[current].maxPricePassed then tmpValue += nodes[j].price - nodes[current].maxPricePassed;
        if (nodes[j].currentPrice = -1) or (tmpValue < nodes[j].currentPrice) then begin
          nodes[j].currentPrice := tmpValue;
          nodes[j].maxPricePassed := max(nodes[current].price, nodes[j].maxPricePassed);
        end;
      end;
    end;
    nodes[current].visited := true;
    minNode := -1;
    for j:=0 to numOfNodes-1 do if (nodes[j].currentPrice > -1) and (not nodes[j].visited) and ((minNode = -1) or (nodes[j].currentPrice < tmpValue)) then begin
      tmpValue := nodes[j].currentPrice;
      minNode := j;
    end;
    if minNode = -1 then exit(-1);
    if minNode = en then exit(nodes[en].currentPrice);
    current := minNode;
  end;
end;

begin
  assign(logFile, 'D:\chiphi_log.txt');
  rewrite(logFile);
  clrscr;
  log(['STAGE 1: Reading data.']);
  assign(f, 'D:\chiphi.inp');
  reset(f);
  readln(f, numOfNodes, numOfPaths, numOfRequests);
  log(['  ', intToStr(numOfNodes), ' nodes; ', intToStr(numOfPaths), ' paths; ', intToStr(numOfRequests), ' requests.']);
  setlength(nodes, numOfNodes);
  log(['  Node prices:']);
  for i:=0 to numOfNodes-1 do begin
    readln(f, nodes[i].price);
    log(['    ', intToStr(i+1), ': ', intToStr(nodes[i].price)]);
    setlength(nodes[i].paths, numOfNodes);
    for tmpNum1 := 0 to numOfNodes-1 do nodes[i].paths[tmpNum1] := -1;
  end;
  log(['  Paths:']);
  for i:=1 to numOfPaths do begin
    readln(f, tmpNum1, tmpNum2, tmpNum3);
    log(['    ', intToStr(tmpNum1), ' <-> ', intToStr(tmpNum2), ': ', intToStr(tmpNum3)]);
    nodes[tmpNum1-1].paths[tmpNum2-1] := tmpNum3;
    nodes[tmpNum2-1].paths[tmpNum1-1] := tmpNum3;
  end;
  log(['  Requests:']);
  setlength(requests, numOfRequests);
  for i:=0 to numOfRequests-1 do begin
    readln(f, tmpNum1, tmpNum2);
    log(['    ', intToStr(tmpNum1), ' -> ', intToStr(tmpNum2)]);
    requests[i].st := tmpNum1-1;
    requests[i].en := tmpNum2-1;
  end;
  close(f);
  log(['']);
  log(['STAGE 2: Analyzing and writing output.']);
  assign(f, 'D:\chiphi.out');
  rewrite(f);
  for i:=0 to numOfRequests-1 do begin
    log(['  Processing request #', intToStr(i+1), ': ', intToStr(requests[i].st+1), ' -> ', intToStr(requests[i].en+1)]);
    tmpNum1 := findLowestPrice(requests[i].st, requests[i].en);
    writeln(f, tmpnum1);
    log(['  Done. Min price: ', intToStr(tmpnum1)]);
  end;
  close(f);
  log(['Done.']);
  close(logFile);
  readln;
end.

Problem statement.md

Problem taken from the 5th Ho Chi Minh City High School Olympic 2018-2019.

Transport cost (CHIPHI)

There is a transport network including N nodes indexed from 1 to N, and M two-way roads connecting them together. Each node has a journey cost T. The cost for moving on each road connecting two nodes I and K is L_IK=L_KI. If one wants to move from a node to another, their cost will be the sum of all crossed roads' costs, plus the highest journey cost of the crossed nodes. This cost may be too big for them, so they have to calculate the minimum cost before deciding to move.

Task: Given transport demand between R pairs of transport nodes, calculate the minimum cost for moving between each pair.

Input: Given in text file CHIPHI.INP, including:

• The first line containing 3 integers N, M, R.
• N next lines, each contains an integer T, which corresponds to the journey cost of transport node 1 to N
• M next lines, each has 3 positive integers I, K and L (I ≠ K) expressing that moving on the road connecting two nodes I and K, will cost L.
• R next lines, each has 2 integers U and V (U ≠ V) expressing the demand of moving from transport node U to transport node V.

Output: Print to text file CHIPHI.OUT, including R lines, each contains a single integer corresponding to the minimum cost for moving between each pair of nodes.

Constraints:

• 1 ≤ N ≤ 250
• 1 ≤ M ≤ 10000
• 1 ≤ R ≤ 10000
• 1 ≤ T ≤ 100000
• 1 ≤ L ≤ 100000

Example

CHIPHI.INP

5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3

CHIPHI.OUT

8
9

Explanation:

Consider a transport network of 5 nodes, 7 two-way roads and 2 pairs of transport nodes on demand.

Detailed costs as follows:

• Journey costs: T₁=2, T₂=5, T₃=3, T₄=3, T₅=4
• Transport costs: L₁₂=3, L₁₃=2, L₂₅=3, L₅₃=1, L₅₄=1, L₂₄=3, L₃₄=4.

Transport demand between 2 pairs of nodes: from node 1 to node 4, from node 2 to node 3.

• To move from node 1 to node 4 with the least cost, nodes need to be crossed in order: 1-3-5-4. The cost is (L₁₃ + L₅₃ + L₅₄) + max{T₁, T₃, T₅, T₄} = (2+1+1)+4 = 8.
• To move from node 2 to node 3 with the least cost, nodes need to be crossed in order: 2-5-3. The cost is (L₂₅ + L₅₃) + max{T₂, T₅, T₃} = (3+1)+5 = 9.