結果

問題 No.1 道のショートカット
ユーザー DSCF_1224_openDSCF_1224_open
提出日時 2018-11-02 16:40:27
言語 Fortran
(gFortran 13.2.0)
結果
WA  
実行時間 -
コード長 8,221 bytes
コンパイル時間 862 ms
コンパイル使用メモリ 36,736 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-08 05:06:18
合計ジャッジ時間 1,964 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

! code created : 2018.11.02
! code updated : 2018.11.02

! 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

	character(len= 49), parameter :: path_working = "E:\Takeharu\GitHub\Fortran\yukicoder\Problem0001\"
	character(len= 12), parameter :: file_setting = "sample03.txt"



	! 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_loads  ! 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_load
	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_loads
		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_loads), stat= statval )
		call exception_allocalte( VAL= statval, NAME= "city_start" )

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

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

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

		allocate( workspace( 0: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= Unitnum_Input, 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= Unitnum_Input, 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= Unitnum_Input, fmt= *, iostat= statval ) cost(:)
		call exception_read( VAL= statval, NAME= "cost" )

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

		! STEP.01.10
		! close the file
		close( unit= Unitnum_Input, 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_loads
		! 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_load = 1, num_loads, 1
						if ( &
							( itr_city .eq. city_start(itr_load) ) .and. &
							( itr_cost+1 - cost(itr_load) .gt. 0 )       &
						) then
							workspace( city_end(itr_load), itr_cost - cost(itr_load) ) &
							= min( &
								workspace( itr_city, itr_cost ) + time(itr_load)           , &
								workspace( city_end(itr_load), itr_cost - cost(itr_load) )   &
							)
						endif
					enddo
				endif
			enddo
		enddo

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

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

		print "(I3)", 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
0