e-olymp 34. Слово спонсора

06/12/2019 by Артем Рогулин

Задача

По завершению турнира «Новогодняя ночь» спонсор решил отправить $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

Код программы

Первый вариант

#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;
}

#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;

}

Второй вариант

#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;
}

#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 (второй вариант кода).

Related Images:

e-olymp 45. Топливо

26/12/2018 by Кирилл Веремйов

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

Входные данные

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

Выходные данные

Единственное число — искомое время.

Тесты

5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4	102
8 10 8 10 8 11 8 0 8 12 8 12 7 8 2 7 6 4 6 2 3 2 1 4 2 3 1 3 1 2 1 5 9 3 5 6 3 4 5 4 5 2	690
11 10 9 5 9 9 9 9 4 9 12 10 10 9 13 3 1 9 1 2 5 2 8 6 2 7 4 1 4 8 4 5 4 4 6 8 1 9 6 9 10 3 10 11 3	520
2 1 3 1 0 6 1 2 10	30
50 50 43 50 44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1 41 42 1 42 43 1 43 44 1 44 45 1 45 46 1 46 44 1 46 48 1 48 49 1 49 50 1 50 1 1	8400
3 3 1 2 3 0 1 1 3 1 2 3 2 1 2 4	6

Решение 1

#include <iostream>
#include <vector>
using namespace std;
    
int n,m,b,c;

struct boil{
    int mass=0;
    int number=0;
    vector<boil*> address;
    vector<int> distance;
};

int empty=0;
int near_tube=0;
vector<int> visit;

int Min_way(boil* A, int i, int from){
    
    if(A[i].mass>b){
        near_tube=A[i].number;
        return 0;
    }

    int min=0;
    
    bool t=0;
    for(int j=0; j< A[i].distance.size(); j++){
        bool t2=true,t1=true;
        for(int u=0; u<visit.size();u++){
            if(visit[u]==A[i].address[j]->number) t2=false;
            if(visit[u]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;
        if(A[i].address[min]->number==empty ||  A[i].address[min]->number==from)t1=false;
        
        if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){
            min=j;
            t=1;
        }
    }
    
    if(t==0){
        if(A[i].distance.size()==1){
            if(A[i].address[0]->mass>b){
                near_tube=A[i].address[0]->number;
                return A[i].distance[0];
            }
            else{
                return -1;
            }
        }
        else return -1;
    }
    else if(A[i].address[min]->mass==b){
        visit.push_back(A[i].number);
        
        bool t1=true;
        long long min2=-1;
        
        for(int k=0; k<visit.size() && t1; k++){
            if(visit[k]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[min]->number==from)t1=false;
        
        if(t1)  min2=Min_way(A,A[i].address[min]->number,A[i].number);
        if(min2>=0)min2+=A[i].distance[min];
            
        int n1=near_tube;
        
        for(int j=0; j<A[i].distance.size(); j++){
            if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){
                visit.push_back(A[i].number);
                long long a=0;
                bool t3=true;
                for(int k=0; k<visit.size() && t3; k++){
                    if(visit[k]==A[i].address[j]->number)t3=false;
                }
                
                if(A[i].address[j]->number==A[empty].number)t3=false;
                
                
                if(t1 && t3){
                    a=Min_way(A,A[i].address[j]->number,A[i].number);
                }
                else return-1;
                if(a>=0)a+=(A[i].distance[j]);
                
                if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){
                    min2=a;
                    n1=near_tube;
                }
                visit.clear();
            }
        }
        near_tube=n1;
        return min2;
    }
    else if(A[i].address[min]->mass<b){
        return -1;
    }
    else{
        near_tube= A[i].address[min]->number;
        return A[i].distance[min];
    }
}

int main() {
    cin>>n>>m>>b>>c;
    boil A[n];
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        A[i].mass=a;
        A[i].number=i;
        if(A[empty].mass>a)empty=i;
    }
    
    int d,k,g;
    while(cin>>d>>k>>g){
            A[d-1].address.push_back(&A[k-1]);
            A[k-1].address.push_back(&A[d-1]);
            A[k-1].distance.push_back(g);
            A[d-1].distance.push_back(g);
    }

    unsigned long long s=0;
    while(A[empty].mass<b){      
        unsigned long long a=Min_way(A,A[empty].number, A[empty].number);
        if(A[near_tube].mass-b+A[empty].mass<b){
            A[empty].mass+=A[near_tube].mass-b;
            s+=a*(A[near_tube].mass-b);
            A[near_tube].mass=b;
        }
        else{
            int tmp=b-A[empty].mass;
            A[near_tube].mass-=tmp;
            A[empty].mass=b;
            s+=a*tmp;
        }
    }
    
    cout<<s*c;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include <iostream>

#include <vector>

using namespace std;

int n,m,b,c;

struct boil{

int mass=0;

int number=0;

vector<boil*> address;

vector<int> distance;

};

int empty=0;

int near_tube=0;

vector<int> visit;

int Min_way(boil* A, int i, int from){

if(A[i].mass>b){

near_tube=A[i].number;

return 0;

}

int min=0;

bool t=0;

for(int j=0; j< A[i].distance.size(); j++){

bool t2=true,t1=true;

for(int u=0; u<visit.size();u++){

if(visit[u]==A[i].address[j]->number) t2=false;

if(visit[u]==A[i].address[min]->number)t1=false;

}

if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;

if(A[i].address[min]->number==empty || A[i].address[min]->number==from)t1=false;

if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){

min=j;

t=1;

}

if(t==0){

if(A[i].distance.size()==1){

if(A[i].address[0]->mass>b){

near_tube=A[i].address[0]->number;

return A[i].distance[0];

}

else{

return -1;

}

else return -1;

}

else if(A[i].address[min]->mass==b){

visit.push_back(A[i].number);

bool t1=true;

long long min2=-1;

for(int k=0; k<visit.size() && t1; k++){

if(visit[k]==A[i].address[min]->number)t1=false;

}

if(A[i].address[min]->number==from)t1=false;

if(t1) min2=Min_way(A,A[i].address[min]->number,A[i].number);

if(min2>=0)min2+=A[i].distance[min];

int n1=near_tube;

for(int j=0; j<A[i].distance.size(); j++){

if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){

visit.push_back(A[i].number);

long long a=0;

bool t3=true;

for(int k=0; k<visit.size() && t3; k++){

if(visit[k]==A[i].address[j]->number)t3=false;

}

if(A[i].address[j]->number==A[empty].number)t3=false;

if(t1 && t3){

a=Min_way(A,A[i].address[j]->number,A[i].number);

}

else return-1;

if(a>=0)a+=(A[i].distance[j]);

if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){

min2=a;

n1=near_tube;

}

visit.clear();

}

near_tube=n1;

return min2;

}

else if(A[i].address[min]->mass<b){

return -1;

}

else{

near_tube= A[i].address[min]->number;

return A[i].distance[min];

}

int main() {

cin>>n>>m>>b>>c;

boil A[n];

for(int i=0; i<n; i++){

int a;

cin>>a;

A[i].mass=a;

A[i].number=i;

if(A[empty].mass>a)empty=i;

}

int d,k,g;

while(cin>>d>>k>>g){

A[d-1].address.push_back(&A[k-1]);

A[k-1].address.push_back(&A[d-1]);

A[k-1].distance.push_back(g);

A[d-1].distance.push_back(g);

}

unsigned long long s=0;

while(A[empty].mass<b){

unsigned long long a=Min_way(A,A[empty].number, A[empty].number);

if(A[near_tube].mass-b+A[empty].mass<b){

A[empty].mass+=A[near_tube].mass-b;

s+=a*(A[near_tube].mass-b);

A[near_tube].mass=b;

}

else{

int tmp=b-A[empty].mass;

A[near_tube].mass-=tmp;

A[empty].mass=b;

s+=a*tmp;

}

cout<<s*c;

return 0;

}

Решение 2

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct boil{
    int mass = 0;
    int len = 0;
    char n/*new*/='y';//yes
    char visit = 'n';//no
    vector <int> link;
    vector <int> dis;
};

int main() {
    int N,M,B,C;
    cin >> N >> M >> B >> C;
    boil A[N];
    int need;
    for(int i = 0; i < N ; i++){
        cin >> A[i].mass;
        if(A[i].mass < B)need = i;
    }
    int a, b, s;
    while(cin >> a >> b >> s){
        a--;
        b--;
        A[a].link.push_back(b);
        A[a].dis.push_back(s);
        A[b].link.push_back(a);
        A[b].dis.push_back(s);
    }
    queue <int> A_tmp;
    A_tmp.push(need);
    A[need].n = 'n';
    int ans = 0;
    while(!(A_tmp.empty())){
        int u = A_tmp.front();
        A_tmp.pop();
        A[u].visit = 'y';//yes
            for(int i = 0;i < A[u].link.size(); i++){ 
                if(A[A[u].link[i]].visit == 'n')
                        A_tmp.push(A[u].link[i]);
                if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){
                    A[A[u].link[i]].len = A[u].len + A[u].dis[i];
                    A[A[u].link[i]].n = 'n';
            }
        }
    }
    while(A[need].mass < B){
        int m = 0;
        for(int i = 0; i < N; i++){
            if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)
                m = i;
        }
        if(A[need].mass + (A[m].mass - B) <= B){
            ans += A[m].len * (A[m].mass - B);
            A[need].mass += A[m].mass - B;
            A[m].mass = B;
        }
        else{
            ans += A[m].len * (B - A[need].mass);
            int b = B - A[need].mass;
            A[need].mass = B;
            A[m].mass -= B - A[need].mass;
        }
    }
    cout << ans * C;
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct boil{

int mass = 0;

int len = 0;

char n/*new*/='y';//yes

char visit = 'n';//no

vector <int> link;

vector <int> dis;

};

int main() {

int N,M,B,C;

cin >> N >> M >> B >> C;

boil A[N];

int need;

for(int i = 0; i < N ; i++){

cin >> A[i].mass;

if(A[i].mass < B)need = i;

}

int a, b, s;

while(cin >> a >> b >> s){

a--;

b--;

A[a].link.push_back(b);

A[a].dis.push_back(s);

A[b].link.push_back(a);

A[b].dis.push_back(s);

}

queue <int> A_tmp;

A_tmp.push(need);

A[need].n = 'n';

int ans = 0;

while(!(A_tmp.empty())){

int u = A_tmp.front();

A_tmp.pop();

A[u].visit = 'y';//yes

for(int i = 0;i < A[u].link.size(); i++){

if(A[A[u].link[i]].visit == 'n')

A_tmp.push(A[u].link[i]);

if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){

A[A[u].link[i]].len = A[u].len + A[u].dis[i];

A[A[u].link[i]].n = 'n';

}

while(A[need].mass < B){

int m = 0;

for(int i = 0; i < N; i++){

if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)

m = i;

}

if(A[need].mass + (A[m].mass - B) <= B){

ans += A[m].len * (A[m].mass - B);

A[need].mass += A[m].mass - B;

A[m].mass = B;

}

else{

ans += A[m].len * (B - A[need].mass);

int b = B - A[need].mass;

A[need].mass = B;

A[m].mass -= B - A[need].mass;

}

cout << ans * C;

return 0;

}

Объяснение 1

Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp

ideone(1)

ideone(2)

Related Images:

A1038. Дейкстра?

06/12/2017 by Калачьов Андрій Сергійович

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

Для 1-го города найти кратчайшие маршруты в остальные города.
В предположении, что каждый город соединен напрямую с каждым, найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города.

Входные данные:

-1	2	4	-1
2	-1	1	6
4	1	-1	1
-1	6	1	-1

Выходные данные:

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

#include <iostream>
#include <climits>
using namespace std;

int main(){
    int n,st=0,sum=0; 
    bool p=true;
    cin>>n;
    int GR[n][n]; 
    int distance[n];
    bool visited[n];    
    int index;
    for (int i=0; i<n; i++){
        distance[i]=INT_MAX; visited[i]=false; 
        for (int j=0; j<n; j++){
            cin>>GR[i][j];
            if (GR[i][j]<0 && i!=j)p=false;
        }
    }    
    if (p==true){
        for (int i=0; i<n-1; i++){
            int minl=INT_MAX;
            for (int j=0; j<n; j++){
                if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];
            }
            sum+=minl;
        }
    }    
    distance[st]=0;
    for (int p=0; p<n-1; p++){
        int min=INT_MAX;
        for (int i=0; i<n; i++){
            if (!visited[i] && distance[i]<min){
                min=distance[i]; index=i;
            }
        }    
        visited[index]=true;
        for (int i=0; i<n; i++){
            if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){
                distance[i]=distance[index]+GR[index][i]; 
            }
        }    
    }
    for (int i=1; i<n; i++){
        if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;
        else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;
    }    
    if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;
    else cout<<"Не все вершины графа соединены";
}

#include <iostream>

#include <climits>

using namespace std;

int main(){

int n,st=0,sum=0;

bool p=true;

cin>>n;

int GR[n][n];

int distance[n];

bool visited[n];

int index;

for (int i=0; i<n; i++){

distance[i]=INT_MAX; visited[i]=false;

for (int j=0; j<n; j++){

cin>>GR[i][j];

if (GR[i][j]<0 && i!=j)p=false;

}

if (p==true){

for (int i=0; i<n-1; i++){

int minl=INT_MAX;

for (int j=0; j<n; j++){

if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];

}

sum+=minl;

}

distance[st]=0;

for (int p=0; p<n-1; p++){

int min=INT_MAX;

for (int i=0; i<n; i++){

if (!visited[i] && distance[i]<min){

min=distance[i]; index=i;

}

visited[index]=true;

for (int i=0; i<n; i++){

if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){

distance[i]=distance[index]+GR[index][i];

}

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

if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;

else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;

}

if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;

else cout<<"Не все вершины графа соединены";

}

Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).

Related Images:

e-olimp 4852. Кратчайшее расстояние

27/06/2016 by Аня Шохина

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex] [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты

Входные данные	Выходные данные
3 1 0 1 0 0 0 0 0 0 0	0 1 -1
6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3 1 0 1 0 1 0 1 0 1 0	0 1 2

Реализация

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    const int inf=4000; // задаем бесконечность 
    int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности 
    cin>>n>>start_position;
    start_position--; // в условии счет начинается с единицы, а в программе с нуля 
    vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины
    for (int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>x;
            if (x==1){
                verges[i].push_back(j);
            }
        }
    }
    bool *used = new bool [n];
    for (int i=0; i<n; i++){
        used[i]=false;
    }
    int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до  i-ой
    for (int i=0; i<n; i++){
        distances[i]=inf; 
    }
    distances[start_position] = 0;
    for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины 
        int minimum=inf;
        int position = 0;
        for (int j=0; j<n; j++){
            if (distances[j]<minimum && !used[j]){
                minimum=distances[j];
                position=j;
            }
        }
        used[position]=true; //запоминаем, что применили алгоритм для вершины 
        for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры 
            distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
        }
    }
    for (int i=0; i<n; i++) {
        cout<<((distances[i]==inf)?-1:distances[i])<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

const int inf=4000; // задаем бесконечность

int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности

cin>>n>>start_position;

start_position--; // в условии счет начинается с единицы, а в программе с нуля

vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины

for (int i=0; i<n; i++){

for(int j=0; j<n; j++){

cin>>x;

if (x==1){

verges[i].push_back(j);

}

bool *used = new bool [n];

for (int i=0; i<n; i++){

used[i]=false;

}

int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой

for (int i=0; i<n; i++){

distances[i]=inf;

}

distances[start_position] = 0;

for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины

int minimum=inf;

int position = 0;

for (int j=0; j<n; j++){

if (distances[j]<minimum && !used[j]){

minimum=distances[j];

position=j;

}

used[position]=true; //запоминаем, что применили алгоритм для вершины

for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры

distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));

}

for (int i=0; i<n; i++) {

cout<<((distances[i]==inf)?-1:distances[i])<<" ";

}

return 0;

}

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

Выходные данные

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

Код программы:

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

for (int i=0; i<G[v].size(); i++) {

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

Для решения использовался алгоритм Дейкстры, подробнее в комментариях к коду.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: алгоритм Дейкстры

e-olymp 34. Слово спонсора

Задача

Входные данные

Выходные данные

Тесты

Код программы

Первый вариант

Второй вариант

Объяснение

К первому варианту кода

Ко второму варианту кода

Ссылки

Related Images:

e-olymp 45. Топливо

Задача

Входные данные

Выходные данные

Тесты

Решение 1

Решение 2

Объяснение 1

Объяснение 2

Related Images:

A1038. Дейкстра?

Related Images:

e-olimp 4852. Кратчайшее расстояние

Входные данные

Выходные данные

Related Images:

e-olimp 4856. Кратчайший путь

Related Images: