Submission #8065542

---

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
			if g[i,j] > 0
				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
					println(i, " ",j)
					x += 1
				end
			end
		end
	end
	println(x)
end

main()

Submission Info

Judge Result