F. Roads in the Kingdom

Codeforces
IDCF835F
Time2000ms
Memory256MB
Difficulty—
dfs and similardpgraphstrees
English · Original
Chinese · Translation
Formal · Original
In the Kingdom K., there are _n_ towns numbered with integers from 1 to _n_. The towns are connected by _n_ bi-directional roads numbered with integers from 1 to _n_. The _i_\-th road connects the towns _u__i_ and _v__i_ and its length is _l__i_. There is no more than one road between two towns. Also, there are no roads that connect the towns with itself. Let's call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns. Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads. ## Input The first line contains the integer _n_ (3 ≤ _n_ ≤ 2·105) — the number of towns and roads. The next _n_ lines contain the roads description. The _i_\-th from these lines contains three integers _u__i_, _v__i_, _l__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, 1 ≤ _l__i_ ≤ 109) — the numbers of towns connected by the _i_\-th road and the length of the _i_\-th road. No road connects a town to itself, no two roads connect the same towns. _It's guaranteed that it's always possible to close down one of the roads so that all the towns are still reachable from each other._ ## Output Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads. [samples]
在王国 K. 中，有 #cf_span[n] 个城镇，编号为从 #cf_span[1] 到 #cf_span[n]。这些城镇通过 #cf_span[n] 条双向道路连接，道路编号为从 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 条道路连接城镇 #cf_span[ui] 和 #cf_span[vi]，其长度为 #cf_span[li]。任意两个城镇之间至多有一条道路，且不存在连接城镇与自身的道路。 我们将道路的不便程度定义为所有城镇对之间最短距离的最大值。 由于资金不足，决定关闭其中一条道路，使得关闭后仍能从任意城镇到达其他任意城镇。你需要找出关闭一条道路后，道路的最小可能不便程度。 第一行包含整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 2·105]) —— 城镇和道路的数量。 接下来的 #cf_span[n] 行描述道路信息。第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[li] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[1 ≤ li ≤ 109]) —— 第 #cf_span[i] 条道路连接的两个城镇编号及其长度。没有道路连接城镇与自身，也没有两条道路连接相同的城镇对。 _保证总能关闭其中一条道路，使得所有城镇仍然相互可达。_ 请输出一个整数 —— 关闭一条道路后，道路的最小可能不便程度。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 2·105]) —— 城镇和道路的数量。接下来的 #cf_span[n] 行描述道路信息。第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[li] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[1 ≤ li ≤ 109]) —— 第 #cf_span[i] 条道路连接的两个城镇编号及其长度。没有道路连接城镇与自身，也没有两条道路连接相同的城镇对。_保证总能关闭其中一条道路，使得所有城镇仍然相互可达。_ ## Output 请输出一个整数 —— 关闭一条道路后，道路的最小可能不便程度。 [samples]
**Definitions** Let $ n \in \mathbb{Z} $, $ 3 \leq n \leq 2 \cdot 10^5 $, be the number of towns and roads. Let $ G = (V, E) $ be an undirected weighted graph where: - $ V = \{1, 2, \dots, n\} $ is the set of towns. - $ E = \{e_1, e_2, \dots, e_n\} $ is the set of roads, where each $ e_i = (u_i, v_i, \ell_i) $, with $ u_i, v_i \in V $, $ u_i \ne v_i $, $ \ell_i \in \mathbb{R}^+ $, and no multiple edges. The graph $ G $ is connected and contains exactly $ n $ edges and $ n $ vertices → $ G $ is a **unicyclic graph** (exactly one cycle). Let $ d_G(u, v) $ denote the shortest path distance between vertices $ u $ and $ v $ in $ G $. Let $ \text{inconvenience}(G) = \max_{u,v \in V} d_G(u, v) $ be the diameter of $ G $. **Constraints** 1. $ G $ is connected and has exactly one cycle. 2. For each edge $ e_i \in E $, removing $ e_i $ results in a connected graph $ G \setminus \{e_i\} $ if and only if $ e_i $ lies on the unique cycle of $ G $. **Objective** Find: $$ \min_{e_i \in C} \text{inconvenience}(G \setminus \{e_i\}) $$ where $ C \subseteq E $ is the set of edges belonging to the unique cycle in $ G $. (Note: Only edges on the cycle can be removed while preserving connectivity.)
Samples
Input #1
3
1 2 4
2 3 5
1 3 1
Output #1
5
Input #2
5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5
Output #2
18
API Response (JSON) 
{
  "problem": {
    "name": "F. Roads in the Kingdom",
    "description": {
      "content": "In the Kingdom K., there are _n_ towns numbered with integers from 1 to _n_. The towns are connected by _n_ bi-directional roads numbered with integers from 1 to _n_. The _i_\\-th road connects the tow",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF835F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the Kingdom K., there are _n_ towns numbered with integers from 1 to _n_. The towns are connected by _n_ bi-directional roads numbered with integers from 1 to _n_. The _i_\\-th road connects the tow...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在王国 K. 中，有 #cf_span[n] 个城镇，编号为从 #cf_span[1] 到 #cf_span[n]。这些城镇通过 #cf_span[n] 条双向道路连接，道路编号为从 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 条道路连接城镇 #cf_span[ui] 和 #cf_span[vi]，其长度为 #cf_span[li]。任意两个城镇之间至多有一条道...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 2 \\cdot 10^5 $, be the number of towns and roads.  \nLet $ G = (V, E) $ be an undirected weighted graph where:  \n- $ V = \\{1, 2, \\dots, n\\} $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac