{"problem":{"name":"F. Find the Length","description":{"content":"For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice. First line of the input contains one inteter n — number of vertices in ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10091F"},"statements":[{"statement_type":"Markdown","content":"For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.\n\nFirst line of the input contains one inteter n — number of vertices in the graph (1 ≤ n ≤ 300).\n\nEach of n lines contain n integers, i-th integer in the i-th column is equal to 0 for any i. If for i ≠ j j-th integer in i-th line aij is equal to  - 1, then vertices i and j are not connected, otherwise they are connected by the edge of weight aij (1 ≤ aij ≤ 106). \n\nYou may assume that graph does not contain self-loops and aij = aji for any 1 ≤ i, j ≤ n.\n\nPrint n integers one per line. i-th of those integers must be lentgh of the shortest simple cycle, containig i-th vertice. If no simple cycles contain i-th vertiex, print  - 1 at corresponding line.\n\n## Input\n\nFirst line of the input contains one inteter n — number of vertices in the graph (1 ≤ n ≤ 300).Each of n lines contain n integers, i-th integer in the i-th column is equal to 0 for any i. If for i ≠ j j-th integer in i-th line aij is equal to  - 1, then vertices i and j are not connected, otherwise they are connected by the edge of weight aij (1 ≤ aij ≤ 106). You may assume that graph does not contain self-loops and aij = aji for any 1 ≤ i, j ≤ n.\n\n## Output\n\nPrint n integers one per line. i-th of those integers must be lentgh of the shortest simple cycle, containig i-th vertice. If no simple cycles contain i-th vertiex, print  - 1 at corresponding line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected weighted graph with $ n = |V| $ vertices, where $ V = \\{1, 2, \\dots, n\\} $.  \nLet $ A \\in \\mathbb{Z}^{n \\times n} $ be the adjacency matrix such that:  \n- $ A_{ii} = 0 $ for all $ i \\in V $,  \n- $ A_{ij} = A_{ji} \\in \\{ -1 \\} \\cup [1, 10^6] $ for all $ i \\ne j $,  \n- $ A_{ij} = -1 $ iff $ (i,j) \\notin E $,  \n- $ A_{ij} = w_{ij} \\ge 1 $ iff $ (i,j) \\in E $ with weight $ w_{ij} $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 300 $  \n2. $ G $ has no self-loops and is symmetric: $ A_{ij} = A_{ji} $  \n3. Edge weights are positive integers: $ w_{ij} \\in [1, 10^6] $  \n\n**Objective**  \nFor each vertex $ v \\in V $, compute:  \n$$\nc_v = \\min \\left\\{ \\sum_{(u,w) \\in C} w_{uw} \\,\\middle|\\, C \\text{ is a simple cycle containing } v \\right\\}\n$$  \nIf no simple cycle contains $ v $, then $ c_v = -1 $.  \n\nOutput $ c_1, c_2, \\dots, c_n $, one per line.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10091F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}