4 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в
километрах) приведена в таблице.
A
D
E
B
4
С
9
2
A
B
С
D
E
4
9
3
2
2
3
2
3
2
2
3
Определите длину кратчайшего пути между пунктами А и Е. Передвигаться можно только
по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить
только один раз.
ответ:
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int> &a_){
vector<int> t;
int n = a_.size();
for(int i = 0; i < n; i++){
int u = i;
for(int j = i + 1; j < n; j++)
if(a_[j] < a_[u])
u = j;
swap(a_[i], a_[u]);
if(!(a_[i] & 1))
t.push_back(a_[i]);
}
a_ = t;
}
void solve(){
vector<int> a = {-2, 4, 10, -1, 1, 6, 3, 7, 8, 5};
insertionSort(a);
cout << "a = {";
for(int i = 0; i < a.size() - 1; i++)
cout << a[i] << ", ";
cout << a.back() << "}";
}
int main(){
solve();
}
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
using namespace std;
void solve(){
srand(time(NULL));
const int N = 10;
vector<int> a(N), d(N + 1, 0);
for(int i = 0; i < N; i++){
a[i] = rand() % 100 + 1;
d[i + 1] = d[i] + a[i];
cout << a[i] << " ";
}
int firstIndex = -1, lastIndex = -1;
for(int i = 0; i < N; i++){
if(!(a[i] & 1)){
if(firstIndex < 0)
firstIndex = i;
lastIndex = i;
}
}
cout << "\n" << d[lastIndex + 1] - d[firstIndex];
}
int main(){
solve();
}