Submission #8065525


Source Code Expand

parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n,m = readline() |> split |> parseMap
	g = zeros(Int,n,n)
	d = 10000000*ones(Int,n,n)
	for i in 1:n
		d[i,i] = 0
	end
	x = 0
	for i in 1:m
		a,b,c = readline() |> split |> parseMap
		g[a,b] = c
		g[b,a] = c
		d[a,b] = c
		d[b,a] = c
	end
	for k in 1:n
		for i in 1:n
			for j in 1:n
				d[i,j] = min(d[i,j],d[i,k]+d[k,j])
			end
		end
	end
	for i in 1:n-1
		for j in i+1:n
			f = 0
			for s in 1:n
				if d[s,i] + g[i,j] == d[s,j]
					f = 1
					break
				end
			end
			if f == 0
				x += 1
			end
		end
	end
	println(x)
end

main()

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User T49E2
Language Julia (0.5.0)
Score 0
Code Size 680 Byte
Status WA
Exec Time 426 ms
Memory 114712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 7
WA × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt
Case Name Status Exec Time Memory
sample_01.txt AC 418 ms 112204 KB
sample_02.txt AC 420 ms 112604 KB
subtask_1_01.txt WA 420 ms 112520 KB
subtask_1_02.txt WA 421 ms 111504 KB
subtask_1_03.txt WA 422 ms 111548 KB
subtask_1_04.txt WA 423 ms 114712 KB
subtask_1_05.txt WA 424 ms 113280 KB
subtask_1_06.txt WA 420 ms 112896 KB
subtask_1_07.txt WA 421 ms 112188 KB
subtask_1_08.txt WA 422 ms 112148 KB
subtask_1_09.txt WA 422 ms 112664 KB
subtask_1_10.txt WA 424 ms 111224 KB
subtask_1_11.txt WA 418 ms 111700 KB
subtask_1_12.txt WA 420 ms 113564 KB
subtask_1_13.txt WA 424 ms 111476 KB
subtask_1_14.txt WA 426 ms 113944 KB
subtask_1_15.txt WA 423 ms 113780 KB
subtask_1_16.txt AC 420 ms 111944 KB
subtask_1_17.txt AC 422 ms 111604 KB
subtask_1_18.txt AC 420 ms 111852 KB
subtask_1_19.txt AC 422 ms 112368 KB
subtask_1_20.txt WA 420 ms 111768 KB
subtask_1_21.txt WA 420 ms 111760 KB
subtask_1_22.txt WA 421 ms 111172 KB
subtask_1_23.txt WA 420 ms 113876 KB
subtask_1_24.txt WA 423 ms 112304 KB
subtask_1_25.txt WA 422 ms 113064 KB
subtask_1_26.txt WA 421 ms 112644 KB
subtask_1_27.txt WA 424 ms 112536 KB
subtask_1_28.txt AC 422 ms 112276 KB