My approach apply bellman and print min distance from 1 to every other, and it passed too, but when I did the same question with Floyd Warshall it gave me WA in some TC’s.
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi dp(n, vi(n,INF));
for (int i = 0; i < n; i++) {
dp[i][i] = 0;
}
And there are compiler flags which enable out of bounds access checks in vector; you don’t have those for array. Any problem where using array gets AC and vector gets TLE are improperly set; both structures have the same time complexity.
In the reading phase you have dp[x][x] = 0; dp[y][y] = 0; this has already been done by the previous initialization.
one more doubt let say we have undirected +ve weighted tree , Now we have to Find two vertices the distance between which is minimum , not need to print vertices just print distance , so what we can do is -
That is the thing, in a tree the minimum simple path between any two vertices is also the maximum simple path between those vertices. Because there are no cycles there is exactly one path between each pair of vertices.