fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7. int n, m, k;
  8. cin >> n >> m >> k; // Количество вершин
  9. vector<int> winner(m);
  10. for (int i = 0; i < m; i++) // Нужные нам вершины
  11. {
  12. cin >> winner[i];
  13. winner[i]--; // Сдвиг индекса, так как у нас отсчёт в задаче начинается с 1, а в коде с нуля
  14. }
  15. vector<vector<int>> path(n, vector<int>(n, 1e6)); // Матрица смежности (1е6 значит, что ребра нет)
  16. for (int i = 0; i < k; i++)
  17. {
  18. int a, b, t;
  19. cin >> a >> b >> t;
  20. a--; //Свдиг индекса
  21. b--;
  22. if (path[a][b] > t)
  23. {
  24. path[a][b] = t;
  25. path[b][a] = t;
  26. }
  27. }
  28. int start; // Вершина, в которой мы находимся
  29. cin >> start;
  30. start--; // Сдвиг индекса
  31. vector<int> count(n, 1e6); // Счётчик пути до вершин
  32. vector<bool> used(n, false); // Посещена ли вершина
  33. count[start] = 0;
  34. while (start != -1) // Алгоритм Дейкстры
  35. {
  36. int next = -1, mini = 1e6;
  37. for (int j = 0; j < n; j++)
  38. {
  39. if (count[j] > count[start] + path[start][j]) // Обновляем расстояние до смежных вершин
  40. {
  41. count[j] = count[start] + path[start][j];
  42. }
  43. if (count[j] < mini && !used[j]) // Ищем непосещённую вершину с минимальным расстоянием
  44. {
  45. next = j;
  46. mini = count[j];
  47. }
  48. }
  49. used[start] = true; // Отмечаем, что данную вершину мы посетили
  50. start = next; // Переходим в следующую вершину
  51. }
  52. bool deliver = true; // Предположим, что посетили все вершины
  53. int longest = 0; // Ставим значение, равное минимальному возможному расстоянию
  54. for (int i = 0; i < m && deliver; i++)
  55. {
  56. if (!used[winner[i]]) // Проверяем всем ли победителям доставили призы
  57. {
  58. deliver = false;
  59. }
  60. longest = max(count[winner[i]], longest); // Ищем максимальную дистанцию
  61. }
  62. if (deliver) // Если доставили призы всем
  63. {
  64. cout << "The good sponsor!\n" << longest;
  65. }
  66. else // Иначе
  67. {
  68. cout << "It is not fault of sponsor...";
  69. }
  70.  
  71. return 0;
  72. }
Success #stdin #stdout 0s 4556KB
stdin
3 2 2
2 3
1 2 3
2 3 4
1
stdout
The good sponsor!
7