325. Опасный маршрут

 

В некотором государстве имеется n городов, некоторые из которых соединены двусторонними дорогами. Города пронумерованы целыми числами от 1 до n. В период финансового кризиса уровень преступности в государстве поднялся и стали появляться организованные преступные группировки. В результате по некоторым дорогам стало опасно ездить.

Бахе надо попасть из города 1 в город n. Так как он слишком ценит свою жизнь (и кошелек), он решил обмануть грабителей и поехать по наименее опасному маршруту, пусть даже он будет не самым коротким. Для каждой дороги он определил ее опасность, как целое число от 0 (безопасная) до 106 (очень опасная). Опасность маршрута – это максимум из опасностей дорог, составляющих маршрут.

Помогите ему выбрать самый безопасный маршрут (то есть тот, опасность которого минимально возможная).

 

Вход. Первая строка содержит два целых числа: n и m (2 ≤ n, m ≤ 106). Каждая из следующих m строк определяет одну дорогу и содержит три целых числа:

·        a, b – города, соединенные дорогой (1 ≤ a, b ≤ n);

·        c – опасность дороги (0 ≤ c ≤ 106).

Любые два города могут быть соединены несколькими дорогами.

 

Выход. Выведите одно целое число – опасность самого безопасного маршрута.

 

Пример входа 1

Пример выхода 1

3 2

1 2 1

2 3 1

1

 

 

Пример входа 2

Пример выхода 2

6 7

1 2 1

2 3 2

3 4 3

4 6 5

2 6 10

2 5 7

5 6 1

5

 

 

РЕШЕНИЕ

структуры данных - система непересекающихся множеств

 

Анализ алгоритма

Отсортируем дороги (ребра графа) по возрастанию их опасности. Для решения задачи будем использовать систему непересекающихся множеств. Изначально образуем n множеств, каждое из которых содержит одну вершину. Просматриваем ребра в порядке возрастания опасности. Для каждого ребра (a, b) объединяем множества, содержащие вершины a и b. Как только вершины 1 и n попадут в одно множество, алгоритм завершается. В этом случае путь от первой вершины до n-ой уже будет существовать, причем опасности дорог, через которые проходит этот путь, будут не большими чем опасность последней рассмотренной дороги. Таким образом если после рассмотрения ребра (x, y) представители вершин 1 и n совпадут, то опасность самого безопасного маршрута будет равна опасности дороги (x, y).

 

Пример

В первом тесте опасность самого безопасного маршрута равна 1.

 

Рассмотрим второй тест.

Ребра обрабатываются в порядке возрастания их опасности. Как только будет обработано ребро с опасностью 5, вершины 1 и 6 соединятся и алгоритм останавливается.

 

Реализация алгоритма

Объявим массив mas, используемый системой непересекающихся множеств. В массиве e будем хранить ребера графа.

 

#define MAX 1000001

int mas[MAX];

struct Edge

{

  int x, y, danger;

} e[MAX];

 

Функция Repr находит представителя множества, в котором находится вершина n. При этом для избежания вердикта Time Limit используется эвристика: если представителем вершины n является x, то следует положить mas[n] = x.

 

int Repr(int n)

{

  if (n == mas[n]) return n;

  return mas[n] = Repr(mas[n]);

}

 

Функция Union объединяет множества, содержащие вершины x и y.

 

int Union(int x,int y)

{

  int x1 = Repr(x),y1 = Repr(y);

  mas[x1] = y1;

  return (x1 != y1);

}

 

Объявим компаратор lt для сравнения ребер. Дороги сортируются по возрастанию их опасности.

 

int lt(Edge a, Edge b)

{

  return (a.danger < b.danger);

}

 

Основная часть программы. Читаем количество городов n и дорог m.

 

scanf("%d %d",&n,&m);

 

Инициализируем массив mas.

 

for(i = 1; i <= n; i++) mas[i] = i;

 

Читаем ребра графа в массив e.

 

for(i = 0; i < m; i++)

  scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].danger);

 

Сортируем ребра по возрастанию опасности.

 

sort(e,e+m,lt);

 

Переберем ребра, начиная с наименее опасного. Объединяем множества, содержащие их вершины. Как только вершины 1 и n попадут в одно множество (Repr(1) станет равным Repr(n)), самый безопасный путь будет найден. Его опасность будет равна опасности последнего обрабатываемого ребра, то есть e[i].danger.

 

for(i = 0; i < m; i++)

{

  Union(e[i].x,e[i].y);

  if (Repr(1) == Repr(n)) break;

}

 

Выводим результат.

 

printf("%d\n",e[i].danger);

 

Java реализация

 

import java.util.*;

 

class Edge

{

  int x, y, danger;

  Edge (int x, int y, int danger)

  {

    this.x = x;

    this.y = y;

    this.danger = danger;

  }

};

 

public class Main

{

  static int mas[], size[];

  static int Repr(int n)

  {

    if (n == mas[n]) return n;

    return mas[n] = Repr(mas[n]);

  }

  static boolean Union(int x,int y)

  {

    x = Repr(x); y = Repr(y);

    if(x == y) return false;

 

    if (size[x] < size[y])

    {

      int temp = x; x = y; y = temp;

    }

    mas[y] = x;

    size[x] += size[y];

    return true;   

  }

 

  public static class MyFun implements Comparator<Edge>

  {

    public int compare(Edge a, Edge b)

    {

      return a.danger - b.danger;

    }

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int m = con.nextInt();

    mas = new int[n+1];

    size = new int[n+1];

   

    for(int i = 1; i <= n; i++)

    {

      mas[i] = i;

      size[i] = 1;

    }

   

    Vector<Edge> v = new Vector<Edge>();

    for(int i = 0; i < m; i++)

    {

      int x = con.nextInt();

      int y = con.nextInt();

      int dust = con.nextInt();

      v.add(new Edge(x,y,dist));

    }

 

    Collections.sort(v, new MyFun());

   

    int index = 0;

    for(int i = 0; i < m; i++)

    {

      Union(v.get(i).x,v.get(i).y);

      if (Repr(1) == Repr(n))

      {

        index = i;

        break;

      }

    }

   

    System.out.println(v.get(index).danger);

    con.close();

  }

}  

 

Python реализация

Объявим структуру ребро Edge.

 

class Edge:

  def __init__(self, x, y, danger):

    self.x = x

    self.y = y

    self.danger = danger

 

Функция Repr находит представителя множества, в котором находится вершина n. При этом для избежания вердикта Time Limit используется эвристика: если представителем вершины n является x, то следует положить mas[n] = x.

 

def Repr(n):

  if n == mas[n]:

    return n

  mas[n] = Repr(mas[n])

  return mas[n]

 

Функция Union объединяет множества, содержащие вершины x и y.

 

def Union(x, y):

  x1 = Repr(x)

  y1 = Repr(y)

  mas[x1] = y1

  return x1 != y1

 

Основная часть программы. Читаем количество городов n и дорог m.

 

n, m = map(int, input().split())

 

Инициализируем список mas, используемый системой непересекающихся множеств.

 

mas = [i for i in range(n + 1)]

 

Читаем ребра графа в список e.

 

e = []

for i in range(m):

  x, y, danger = map(int, input().split())

  e.append(Edge(x, y, danger))

 

Сортируем ребра по возрастанию опасности.

 

e.sort(key=lambda x: x.danger)

 

Переберем ребра, начиная с наименее опасного. Объединяем множества, содержащие их вершины. Как только вершины 1 и n попадут в одно множество (Repr(1) станет равным Repr(n)), самый безопасный путь будет найден. Его опасность будет равна опасности последнего обрабатываемого ребра, то есть e[i].danger.

 

for i in range(m):

  Union(e[i].x, e[i].y)

  if Repr(1) == Repr(n):

    break

 

Выводим результат.

 

print(e[i].danger)