Submission #8065537

---

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
		for j in 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>>1)
end

main()

Submission Info

Judge Result