On k-Connectivity Problems with Sharpened Triangle Inequality