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