选项A是正确的，建网的时间复杂度确实为O(n^2 + n + e*n)，其中n^2是邻接矩阵的初始化，n是顶点的处理，e*n是弧的处理。选项B错误，因为没有考虑到邻接矩阵的初始化时间。选项C虽然提到O(n^2)，但忽略了弧的处理时间，因此不完整。选项D错误，因为时间复杂度不仅仅取决于弧的数量，还包括初始化和顶点处理的时间。因此，正确答案是A。