Problem: Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are described by a grid of characters S. If S_{i,j} is `1`, there is an edge connecting Vertex i and j; otherwise, there is no such edge.  Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k, in such a division.    * Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j), there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.

Submission attempts (in order):
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, dijkstra
# G = csgraph_from_dense(edge, null_value=10**9)
# f = floyd_warshall(G)

import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[(xs,ys,0),(xt,yt,0)]
data=[[-1]*(n+2) for i in range(n+2)]
for i in range(n):
    xyr.append(tuple(map(int,input().split())))
# print(xyr)

for i in range(n+1):
    for j in range(i+1,n+2):
        x0 = xyr[i][0]
        y0 = xyr[i][1]
        r0 = xyr[i][2]
        x1 = xyr[j][0]
        y1 = xyr[j][1]
        r1 = xyr[j][2]
        data[i][j]=max(((x0-x1)**2+(y0-y1)**2)**.5-r0-r1,0)

G = csgraph_from_dense(data, null_value=-1)

#     print(i)
d = dijkstra(G, indices=0, directed=False)
print(d[1])



#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
def solve():
    n=int(input())
    data=[list(map(int,list(input()))) for i in range(n)]
    fordfs=[[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j]==1:
                fordfs[i].append(j)

    def dfs():
        V=[-1]*n
        V[0]=0
        que=deque()
        que.append(0)
        while que:
            now=que.popleft()
            nowv=V[now]
            for ne in fordfs[now]:
                if nowv==V[ne]:
                    print(-1)
                    exit()
                elif V[ne]==-1:
                    V[ne]=(nowv+1)%2
                    que.append(ne)
    
    dfs()
    # print(data)
    G=csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M=0
    for i in d:
        M=max(M,max(i))
    M=int(M)
    print(M+1)
    return



def main():

    solve()
    return
if __name__ == '__main__':
    main()



#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)



def main():

    n = int(input())


    data = [list(map(int, list(input()))) for i in range(n)]
    fordfs = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j] == 1:
                fordfs[i].append(j)


    def bfs():
        V = [-1]*n
        V[0] = 0
        que = deque()
        que.append(0)
        while que:
            now = que.popleft()
            nowv = V[now]
            for ne in fordfs[now]:
                if nowv == V[ne]:
                    print(-1)
                    exit()
                elif V[ne] == -1:
                    V[ne] = (nowv+1) % 2
                    que.append(ne)


    bfs()
    # print(data)
    G = csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M = 0
    for i in d:
        M = max(M, max(i))
    M = int(M)
    print(M+1)
    return
if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Runtime Error

Accepted