#295723 (Fortran) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	DSCF_1224_open
提出日時	2018-11-02 17:22:02
言語	Fortran (gFortran 13.2.0)
結果	AC
実行時間	8 ms / 5,000 ms
コード長	8,107 bytes
コンパイル時間	206 ms
コンパイル使用メモリ	30,320 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-27 22:17:38
合計ジャッジ時間	1,600 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	3 ms 4,380 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	4 ms 4,380 KB
testcase_12	AC	7 ms 4,376 KB
testcase_13	AC	8 ms 4,376 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	1 ms 4,380 KB
testcase_17	AC	1 ms 4,380 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,376 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	1 ms 4,380 KB
testcase_23	AC	4 ms 4,376 KB
testcase_24	AC	4 ms 4,380 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	5 ms 4,376 KB
testcase_28	AC	1 ms 4,380 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	1 ms 4,380 KB
testcase_32	AC	3 ms 4,376 KB
testcase_33	AC	1 ms 4,380 KB
testcase_34	AC	3 ms 4,376 KB
testcase_35	AC	1 ms 4,380 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	1 ms 4,376 KB
testcase_41	AC	1 ms 4,380 KB
testcase_42	AC	1 ms 4,376 KB
testcase_43	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

! yukicoder Problem 0001
! 
! code created : 2018.11.02
! code updated : 2018.11.02
! 
! [reference]
! http://mmxsrup.hatenablog.com/entry/2016/07/16/111859


! http://numerical.recipes/pubdom/nrtype.f90.txt
MODULE nrtype

	! Require all variables to be explicitly declared
	implicit none

	integer, parameter :: I4B = SELECTED_INT_KIND(9)
	integer, parameter :: I2B = SELECTED_INT_KIND(4)
	integer, parameter :: I1B = SELECTED_INT_KIND(2)
	integer, parameter :: SPR = KIND(1.0)
	integer, parameter :: DPR = KIND(1.0D0)
	integer, parameter :: SPC = KIND((1.0,1.0))
	integer, parameter :: DPC = KIND((1.0D0,1.0D0))
	integer, parameter :: LGT = KIND(.true.)

END MODULE nrtype



module Exception

	! import modules to use
	USE nrtype

	! Require all variables to be explicitly declared
	implicit none

	contains

	! Exception for the `stat` of <allocate> statement
	subroutine exception_allocalte( val, name )

		! declaration of the arguments
		integer(kind= I4B), intent(in) :: val  ! return value of the <STAT>
		character(len= *),  intent(in) :: name ! name of the target array

		if ( val .gt. 0 ) then
			print "(A)"  , "Error allocating `" // name // "`"
			print "(A,I3)", "<STAT> is", val
			call stop_simple
		else
			return
		endif

	end subroutine exception_allocalte

	! Exception for the `stat` of <deallocate> statement
	subroutine exception_deallocalte( val, name )

		! declaration of the arguments
		integer(kind= I4B), intent(in) :: val  ! return value of the <STAT>
		character(len= *),  intent(in) :: name ! name of the target array

		if ( val .gt. 0 ) then
			print "(A)"  , "Error deallocating `" // name // "`"
			print "(A,I3)", "<STAT> is", val
			call stop_simple
		else
			return
		endif

	end subroutine exception_deallocalte

	! Exception for the `iostat` of <read> statement
	subroutine exception_read( val, name )

		! declaration of the arguments
		integer(kind= I4B), intent(in) :: val  ! return value of the <IOSTAT>
		character(len= *),  intent(in) :: name ! name of the target array

		if ( val .gt. 0 ) then
			print "(A)"  , "Error reading `" // name // "`"
			print "(A,I3)", "<STAT> is", val
			call stop_simple
		else
			return
		endif

	end subroutine exception_read

	! <STOP> statement with fixed and simple comment
	subroutine stop_simple
		stop "<STOP> statement have been activated!"
	end subroutine stop_simple
	

end module Exception



! Main Process
program main

	! import modules to use
	USE nrtype
	USE Exception

	! Require all variables to be explicitly declared
	implicit none

	! constants in this <program>
	integer(kind= I4B), parameter :: Unitnum_Input = 10




	! variables in this <program>
	integer(kind= I4B) :: num_cities ! the number of the cities
	integer(kind= I4B) :: lim_cost   ! the limit of the cost
	integer(kind= I4B) :: inf_cost   ! the upper range of data type of `cost`
	integer(kind= I4B) :: num_roads  ! the number of the loads
	integer(kind= I4B) :: sum_time   ! the total time of the most suitable route

	integer(kind= I4B), dimension(:), allocatable :: city_start ! index of the city of the start of load
	integer(kind= I4B), dimension(:), allocatable :: city_end   ! index of the city of the end of load
	integer(kind= I4B), dimension(:), allocatable :: cost       ! cost of the load to pass
	integer(kind= I4B), dimension(:), allocatable :: time       ! time of the load to pass

	integer(kind= I4B), dimension(:,:), allocatable :: workspace ! work space for dynamic programming

	! support variables in this <program>
	integer(kind= I4B) :: itr_city, itr_cost, itr_road
	integer(kind= I4B) :: statval

	character(len= 128) :: buff_msg

	! STEP.01
	! get the settings of the problem

		! STEP.01.01
		! open the data file
		! open( & 
		! 	unit        = Unitnum_Input , &
		! 	defaultfile = path_working  , & 
		! 	file        = file_setting  , &
		! 	iostat      = statval       , & 
		! 	status      = "old"         , &
		! 	action      = "read"          &
		! )

		! if ( statval .ne. 0 ) stop "Error opening " // path_working // file_setting



		! STEP.01.02
		! read out the number of the cities
		read( unit= *, fmt= *, iostat= statval ) num_cities
		if ( statval .ne. 0 ) stop "Error reading `the number of the cities`" 

		! STEP.01.03
		! read out the limit of the cost
		read( unit= *, fmt= *, iostat= statval ) lim_cost
		if ( statval .ne. 0 ) stop "Error reading `the limit of the cost`" 

		! STEP.01.04
		! read out the number of the loads
		read( unit= *, fmt= *, iostat= statval ) num_roads
		if ( statval .ne. 0 ) stop "Error reading `the number of the loads`" 

		! STEP.01.05
		! allocate the arrays to store data of the problem setting
		allocate( city_start(1:num_roads), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "city_start" )

		allocate( city_end(1:num_roads), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "city_end" )

		allocate( cost(1:num_roads), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "cost" )

		allocate( time(1:num_roads), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "time" )

		allocate( workspace( 1:num_cities, 0:lim_cost ), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "work space" )



		! STEP.01.06
		! read out the number of the city as the start of the load
		read( unit= *, fmt= *, iostat= statval ) city_start(:)
		call exception_read( VAL= statval, NAME= "city_start" )

		! STEP.01.07
		! read out the number of the city as the end of the load
		read( unit= *, fmt= *, iostat= statval ) city_end(:)
		call exception_read( VAL= statval, NAME= "city_end" )

		! STEP.01.08
		! read out the cost of the load
		read( unit= *, fmt= *, iostat= statval ) cost(:)
		call exception_read( VAL= statval, NAME= "cost" )

		! STEP.01.09
		! read out the time of the load
		read( unit= *, fmt= *, iostat= statval ) time(:)
		call exception_read( VAL= statval, NAME= "time" )

		! STEP.01.10
		! close the file
		! close( unit= *, iostat= statval, status="keep" )
		! if ( statval .ne. 0 ) stop "Error closing file" // path_working // file_setting

		! STEP.01.??
		! output the read out values
		! print     "(I5)", num_cities
		! print     "(I5)", lim_cost
		! print     "(I5)", num_roads
		! print   "(50I5)", city_start
		! print   "(50I5)", city_end
		! print  "(300I5)", cost
		! print "(1000I5)", time

	! STEP.02
	! calculation the minimum time

		! STEP.02.01
		! initialize the work space for dynamic programming
		inf_cost              = huge( inf_cost )
		workspace(:,:)        = inf_cost
		workspace(1,lim_cost) = 0

		! STEP.02.02
		! calculate the target using dynamic programming
		do itr_city = 1, num_cities, 1
			do itr_cost = lim_cost, 0, -1
				if ( workspace( itr_city, itr_cost ) .ne. inf_cost ) then
					do itr_road = 1, num_roads, 1
						if ( &
							( itr_city .eq. city_start(itr_road) ) .and. &
							( itr_cost - cost(itr_road) .ge. 0 )         &
						) then
							workspace( city_end(itr_road), itr_cost - cost(itr_road) ) &
							= min( &
								workspace( itr_city, itr_cost ) + time(itr_road)           , &
								workspace( city_end(itr_road), itr_cost - cost(itr_road) )   &
							)
						endif
					enddo
				endif
			enddo
		enddo

		! STEP.02.03
		! calculate the total time of the most suitable route
		sum_time = minval( workspace(num_cities,:), inf_cost )

		if ( sum_time .ge. huge(sum_time) ) then
			sum_time = -1
		endif

		print *, sum_time

	! STEP.03
	! deallocate the arrays to store data of the problem setting
	deallocate( city_start, stat= statval ); call exception_deallocalte( VAL= statval, NAME= "city_start" )
	deallocate(   city_end, stat= statval ); call exception_deallocalte( VAL= statval, NAME= "city_end" )
	deallocate(       cost, stat= statval ); call exception_deallocalte( VAL= statval, NAME= "cost" )
	deallocate(       time, stat= statval ); call exception_deallocalte( VAL= statval, NAME= "time" )
	deallocate(  workspace, stat= statval ); call exception_deallocalte( VAL= statval, NAME= "work space" )

	! STEP.END
	! print *, ""
	! print *, "All processes have finished successfully."

end program main