module mod_t_item
  implicit none
  type :: t_item
    integer :: pos
    integer(8) :: cost
  end type t_item
  private
  public :: t_item, itemize, compare, swap
contains
  function itemize(pos,cost) result(i)
    implicit none
    integer :: pos
    integer(8) :: cost
    type(t_item) :: i
    i%pos = pos
    i%cost = cost
    return
  end function itemize
  function compare(i1,i2) result(c)
    implicit none
    type(t_item), intent(in) :: i1, i2
    integer(8) :: c
    c = i1%cost-i2%cost
    return
  end function compare
  subroutine swap(i1,i2)
    implicit none
    type(t_item), intent(inout) :: i1, i2
    type(t_item) :: i
    i = i1
    i1 = i2
    i2 = i
    return
  end subroutine swap
end module mod_t_item
module mod_t_list
  use mod_t_item
  implicit none
  type :: t_list
    integer :: vol
    type(t_item), pointer :: arr(:)
  end type t_list
  private
  public :: t_list, init_list, release_list,push_back
  public :: pop_back, get_at, size_of_list
contains
  subroutine init_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = 0
    allocate(list%arr(1))
    return
  end subroutine init_list
  subroutine release_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    if (associated(list%arr)) deallocate(list%arr)
    return
  end subroutine release_list
  subroutine push_back(list,item)
    implicit none
    type(t_list), intent(inout) :: list
    type(t_item), intent(in) :: item
    type(t_item), allocatable :: tmp(:)
    if (size(list%arr).eq.list%vol) then
      allocate(tmp(list%vol))
      tmp = list%arr
      deallocate(list%arr)
      allocate(list%arr(2*list%vol))
      list%arr(1:list%vol) = tmp
      deallocate(tmp)
    end if
    list%vol = list%vol+1
    list%arr(list%vol) = item
    return
  end subroutine push_back
  function pop_back(list) result(item)
    implicit none
    type(t_list), intent(inout) :: list
    type(t_item) :: item
    item = list%arr(list%vol)
    list%vol = list%vol-1
    return
  end function pop_back
  function get_at(list,i) result(item)
    implicit none
    type(t_list), intent(in) :: list
    integer, intent(in) :: i
    type(t_item) :: item
    item = list%arr(i)
    return
  end function get_at
  function size_of_list(list) result(s)
    implicit none
    type(t_list), intent(in) :: list
    integer :: s
    s = list%vol
    return
  end function size_of_list
end module mod_t_list
module mod_t_priority_queue
  use mod_t_item
  use mod_t_list
  implicit none
  type :: t_heap
    type(t_list) :: list
  end type t_heap
  private
  public :: t_heap, init_heap, release_heap, push, pop, size_of_heap
contains
  subroutine init_heap(heap)
    implicit none
    type(t_heap), intent(inout) :: heap
    call init_list(heap%list)
    return
  end subroutine init_heap
  subroutine release_heap(heap)
    implicit none
    type(t_heap), intent(inout) :: heap
    call release_list(heap%list)
    return
  end subroutine release_heap
  subroutine push(heap,item)
    implicit none
    type(t_heap), intent(inout) :: heap
    type(t_item), intent(in) :: item
    integer :: n, i
    call push_back(heap%list,item)
    n = heap%list%vol
    do while (n.gt.1)
      i = n/2
      if (compare(heap%list%arr(n),heap%list%arr(i)).lt.0_8) then
        call swap(heap%list%arr(n),heap%list%arr(i))
      end if
      n = i
    end do
    return
  end subroutine push
  function pop(heap) result(item)
    implicit none
    type(t_heap), intent(inout) :: heap
    type(t_item) :: item, tmp
    integer :: n, i, j
    n = heap%list%vol
    item = heap%list%arr(1)
    heap%list%arr(1) = heap%list%arr(n)
    tmp = pop_back(heap%list)
    i = 1
    do while (2*i.lt.n)
      j = 2*i
      if ((j.lt.n-1).and.(compare(heap%list%arr(j+1),heap%list%arr(j)).lt.0_8)) then
        j = j+1
      end if
      if (compare(heap%list%arr(j),heap%list%arr(i)).lt.0_8) then
        call swap(heap%list%arr(j),heap%list%arr(i))
      end if
      i = j
    end do
    return
  end function pop
  function size_of_heap(heap) result(s)
    implicit none
    type(t_heap), intent(in) :: heap
    integer :: s
    s = size_of_list(heap%list)
    return
  end function size_of_heap
end module mod_t_priority_queue
module mod_t_graph
  use mod_t_item
  use mod_t_list
  use mod_t_priority_queue
  implicit none
  integer(8), parameter :: infty = 10000000000000000_8
  type :: t_graph
    type(t_list), pointer :: edges(:)
  end type t_graph
  private
  public :: infty
  public :: t_graph, init_graph, release_graph, add_edge, add, dijkstra
contains
  subroutine init_graph(graph,n)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: n
    integer :: i
    allocate(graph%edges(n))
    do i = 1, n
      call init_list(graph%edges(i))
    end do
    return
  end subroutine init_graph
  subroutine release_graph(graph)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer :: n, i
    if (.not.associated(graph%edges)) return
    n = size(graph%edges)
    do i = 1, n
      call release_list(graph%edges(i))
    end do
    deallocate(graph%edges)
    return
  end subroutine release_graph
  subroutine add_edge(graph,i,edge)
    implicit none
    type(t_graph), intent(inout) :: graph
    type(t_item), intent(in) :: edge
    integer, intent(in) :: i
    call push_back(graph%edges(i),edge)
    return
  end subroutine add_edge
  subroutine add(graph,i,pos,cost)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: i, pos
    integer(8), intent(in) :: cost
    call push_back(graph%edges(i),itemize(pos,cost))
    return
  end subroutine add
  function dijkstra(graph,start) result(c)
    implicit none
    type(t_graph), intent(in) :: graph
    integer, intent(in) :: start
    type(t_heap) :: pq
    type(t_item) :: now, next
    integer :: n, i
    integer(8) :: c(size(graph%edges))
    n = size(graph%edges)
    c = infty
    call init_heap(pq)
    c(start) = 0_8
    call push(pq,itemize(start,0_8))
    do while (size_of_heap(pq).gt.0)
      now = pop(pq)
      if (now%cost.gt.c(now%pos)) cycle
      do i = 1, size_of_list(graph%edges(now%pos))
        next = get_at(graph%edges(now%pos),i)
        if (c(next%pos).gt.c(now%pos)+next%cost) then
          c(next%pos) = c(now%pos)+next%cost
          call push(pq,itemize(next%pos,c(next%pos)))
        end if
      end do
    end do
    call release_heap(pq)
    return
  end function dijkstra
end module mod_t_graph
program saving_snuuk
  use mod_t_graph
  implicit none
  type(t_graph) :: yen_graph, snuuk_graph
  integer(8), parameter :: dyen = 1000000000000000_8
  integer :: n, m, s, t, u, v, i
  integer(8) :: a, b, yen(100000), snuuk(100000), cost(100000)
  yen = 0_8
  snuuk = 0_8
  cost = 0_8
  read(*,*) n, m, s, t
  call init_graph(yen_graph,n)
  call init_graph(snuuk_graph,n)
  do i = 1, m
    read(*,*) u, v, a, b
    call add(yen_graph,u,v,a)
    call add(yen_graph,v,u,a)
    call add(snuuk_graph,u,v,b)
    call add(snuuk_graph,v,u,b)
  end do
  yen(1:n) = dijkstra(yen_graph,s)
  snuuk(1:n) = dijkstra(snuuk_graph,t)
  cost(n) = yen(n)+snuuk(n)
  do i = n-1, 1, -1
    cost(i) = min(cost(i+1),yen(i)+snuuk(i))
  end do
  do i = 1, n
    write(*,'(i0)') dyen-cost(i)
  end do
  call release_graph(yen_graph)
  call release_graph(snuuk_graph)
  stop
end program saving_snuuk

Measured memory_bytes: 26864