I. Coin Robbery

Codeforces

IDCF10053I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Steve is a prominent coin collector and John is a professional thief, but Steve is not aware of this fact. They make friends and someday Steve asks John to help him move his coins to some other place. At the middle of the movement John plans a robbery and takes all Steve's coins. He has planned to go to airport and run away to Somalia as soon as possible. This is the live conversation between Police station and Police officer. *Police Station*: #cf_span(class=[tex-font-style-underline], body=[We have found John's flight number, he is a mother lover, he wants to dedicate these coins to his mother in Somalia. he will use airport to run away to Somalia.]) *Police Officer*: #cf_span(class=[tex-font-style-underline], body=[So ask airport security to arrest him.]) *Police Station*: #cf_span(class=[tex-font-style-underline], body=[Right now we have no authority in airport. We have to do something in the city to arrest him out of airport or delay his arrival to the airport so he will miss his flight. John is smart, he has planned to arrive in airport and catch his plane with no delay in between.]) *Police Officer*: #cf_span(class=[tex-font-style-underline], body=[We have some police officers in all intersections, we need to inform them to make block some intersections.]) We can not block starting intersection nor ending intersection (airport). Intersections are numbered from 0 to n - 1. John starts his path from intersection 0 (John's starting intersection is intersection [number] 0) and airport is in intersection [number] n - 1. Now it's your turn, inform minimum number of police officers at intersections so that we can arrest John in one of the intersections or we can delay his arrival to airport so that he will miss his flight. First line of input contains two integers, n and m, the number of intersections and the number of streets, correspondingly. Each of the next m lines contains a description of a bidirectional street, two ends of the street and the length of the street. (2 ≤ n ≤ 100) (1 ≤ m ≤ 10000) (1 ≤ length of each street ≤ 100) If it's impossible to block John from entering airport, print IMPOSSIBLE, otherwise print the minimum number of intersections we need to block. ## Input First line of input contains two integers, n and m, the number of intersections and the number of streets, correspondingly. Each of the next m lines contains a description of a bidirectional street, two ends of the street and the length of the street. (2 ≤ n ≤ 100) (1 ≤ m ≤ 10000) (1 ≤ length of each street ≤ 100) ## Output If it's impossible to block John from entering airport, print IMPOSSIBLE, otherwise print the minimum number of intersections we need to block. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected weighted graph, where: - $ V = \{0, 1, \dots, n-1\} $ is the set of intersections. - $ E $ is the set of bidirectional streets, each $ (u, v, w) \in E $ with weight $ w \in \mathbb{Z}^+ $. - Source: $ s = 0 $, Sink: $ t = n-1 $. **Constraints** 1. $ 2 \leq n \leq 100 $ 2. $ 1 \leq m \leq 10000 $ 3. $ 1 \leq w \leq 100 $ for all edges 4. Cannot block $ s $ or $ t $. **Objective** Find the minimum number of vertices (intersections) to remove (excluding $ s $ and $ t $) such that there is no path from $ s $ to $ t $ in $ G $. If no such vertex cut exists, output `IMPOSSIBLE`.

API Response (JSON)

{
  "problem": {
    "name": "I. Coin Robbery",
    "description": {
      "content": "Steve is a prominent coin collector and John is a professional thief, but Steve is not aware of this fact. They make friends and someday Steve asks John to help him move his coins to some other place.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10053I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Steve is a prominent coin collector and John is a professional thief, but Steve is not aware of this fact. They make friends and someday Steve asks John to help him move his coins to some other place....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected weighted graph, where:  \n- $ V = \\{0, 1, \\dots, n-1\\} $ is the set of intersections.  \n- $ E $ is the set of bidirectional streets, each $ (u, v, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments