Города и дороги

@aassii · Регистрация: 12.10.2018

Студворк — интернет-сервис помощи студентам

Семицарство состоит из n городов, занумерованных целыми числами от 1 до n. Столица Семицарства - Король-Берег, и она имеет номер 1. Города Семицарства соединены m двусторонними дорогами длины 1, причем между каждой парой городов не может быть больше 2-х дорог, и ни одна дорога не может соединять город с самим собой. От вас требуется найти расстояния до всех городов от города с номером 1, или сказать, что добраться до него дорогами невозможно.

Входные данные:
В первой строке входного файла содержатся 2 целые числа n и m (1<=n<=10^5, 0<=m<=min(10^5, n(n-1)/2)) - количество городов и количество дорог между ними. В следующих m строках содержатся по 2 целые числа u, v в каждом (1 ≤ u, v ≤ n, u ≠ v), что означает, что мост u i v соединены двусторонней дорогой.

Исходные данные:
В единственной строке выведите n чисел di (- 1 ≤ di ≤ n - 1) - расстояние от города с номером один в города с номером i, или -1, если добраться до города дорогами невозможно.

Пример:

Кликните здесь для просмотра всего текста

Ввод
8 8
1 2
2 3
3 4
2 4
5 7
6 7
6 8
5 8
Вывод
0 1 2 2 -1 -1 -1 -1

@ReDoX · 27.02.2019, 20:02

Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры

C++
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
const int INF = 1000000000;
 
int main() {
    int n;
    ... чтение n ...
    vector < vector < pair<int,int> > > g (n);
    ... чтение графа ...
    int s = ...; // стартовая вершина
 
    vector<int> d (n, INF),  p (n);
    d[s] = 0;
    vector<char> u (n);
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        u[v] = true;
 
        for (size_t j=0; j<g[v].size(); ++j) {
            int to = g[v][j].first,
                len = g[v][j].second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

@aassii · 01.03.2019, 23:16 **[ТС]**

ReDoX, подскажите пожалуйста, где наделал ошибки?

C++
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
int main() {
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector < vector < pair<int,int> > > g (n);
    for (int j=0; j<n; ++j)
    {
        int u,v;
        cin>>u>>v;
        g[j].push_back(make_pair(u,v));
    }
    int s = 1;
    vector<int> d (n, INF),  p (n);
    d[s] = 0;
    vector<char> u (n);
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        u[v] = true;
 
        for (size_t j=0; j<g[v].size(); ++j) {
            int to = g[v][j].first,
                len = g[v][j].second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
    int t=1;
    vector<int> path;
    for (int v=t; v!=s; v=p[v])
        path.push_back (v);
    path.push_back (s);
    reverse (path.begin(), path.end());
    for (int j=0; j<n; ++j)
    {
        cout<<path[j]<<" ";
    }
    return 0;
}

@ReDoX · 01.03.2019, 23:45

aassii, в графах совершенно ничего не понимаю, но вот, что получилось сделать:

C++
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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max();
int main() {
  int n;
  int m;
  cin >> n >> m;
 
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int from;
    int to;
    cin >> from >> to;
 
    --from;
    --to;
 
    g[from].push_back({to, 1});
    g[to].push_back({from, 1});
  }
 
  int s = 0;
  vector<int> d(n, INF);
  vector<int> p(n);
 
  d[s] = 0;
 
  vector<char> u(n);
  for (int i = 0; i < n; ++i) {
    int v = -1;
 
    for (int j = 0; j < n; ++j) {
      if (!u[j] && (v == -1 || d[j] < d[v]))
        v = j;
    }
 
    if (d[v] == INF)
      break;
 
    u[v] = true;
 
    for (size_t j = 0; j < g[v].size(); ++j) {
      int to = g[v][j].first, len = g[v][j].second;
      if (d[v] + len < d[to]) {
        d[to] = d[v] + len;
        p[to] = v;
      }
    }
  }
 
  cout << 0 << ' ';
 
  for (int i = 1; i < n; ++i) {
    vector<int> path;
    for (int v = i; v != s; v = p[v])
      path.push_back(v);
 
    if (path.empty()) {
      cout << -1;
    } else {
      cout << path.size();
    }
 
    cout << ' ';
  }
}

Почему-то в несуществующих путях выводит 1.

Возможен следующий костыль:

1. Построить компоненту связности от 0 вершины (стартовый город)
2. Если 1, 2, 3... вершины входят в эту компоненту, то вывести длину пути, иначе вывести -1.

@aassii · 02.03.2019, 00:23 **[ТС]**

В моем програмном коде выводится мусор, потому, что после инициализации вектора я не обнулил все его елементы.
Как это можно сделать? (например через memset)

@ReDoX · 02.03.2019, 01:31

Сообщение от aassii

Как это можно сделать?

fill

или конструктор vector'а:

C++
1
2
3
4
5
6
vector<int> a(n, 100);
 
// работаем с вектором...
 
// обнуляем
a = vector<int>(n, 0);

Вы неправильно вводите данные, поэтому и мусор выводится. На ввод подаются две вершины, а не вершина и вес. По задаче граф невзвешенный. Гугл говорит, что, чтобы алгоритм работал, нужно брать вершины с весом (например, 1)

@aassii · 02.03.2019, 02:34 **[ТС]**

Сообщение от ReDoX

Вы неправильно вводите данные, поэтому и мусор выводится.

Можете помочь правильно ввести данные?

Добавлено через 36 минут
fill(g.begin(), g.end(), 0); - это для линейного вектора.

А как правильно использовать fill и конструктор (для обнуления) для такого вектора пар:
vector < vector < pair<int,int> > > g (n); ?

@ReDoX · 02.03.2019, 12:00

Сообщение от aassii

Можете помочь правильно ввести данные?

Я скинул код с правильным вводом

Сообщение от aassii

А как правильно использовать fill и конструктор (для обнуления) для такого вектора пар:
vector < vector < pair<int,int> > > g (n); ?

C++
1
2
3
for (auto& i : g) {
  i = vector<pair<int, int>>(i.size(), {0, 0});
}

@aassii · 02.03.2019, 20:29 **[ТС]**

Сообщение от ReDoX

Почему-то в несуществующих путях выводит 1.

Потому что вектор path никогда не бывает пустой.
Гляньте:

C++
1
2
for (vector<int>::const_iterator it = path.begin(); it != path.end(); ++it )
        {cout<<"it="<<*it<<" ";}

@ReDoX · 02.03.2019, 21:07

Сообщение от aassii

Потому что вектор path никогда не бывает пустой.

Дело даже не в этом

Посмотрите на кратчайшие пути, которые построил алгоритм:

C++
1
2
3
4
5
6
7
8
1 // от 2 до 1 и т.д.
1 2  // От 3 до 1. ПОКА ВСЕ ОК
1 3 // ??? КАКИМ ОБРАЗОМ???
// В чем смысл остального вывода? Какой это кратчайший путь до вершины?
4
5
6
7

Возможен еще один - в приложение к тому, что я публиковал выше - костыль:

C++
1
2
3
4
5
if (find(path.cbegin(), path.cend(), 1) != path.cend()) {
  // Путь есть, наверное...
} else {
  // пути нет...
}

Если со всеми костылями не работает, то можно решить в лоб - поиск в ширину. На емаксе есть сам алгоритм и то, как получить кратчайший путь, но по времени это будет очень неэффективно

@aassii · 05.03.2019, 16:53 **[ТС]**

Сообщение от ReDoX

Возможен еще один - в приложение к тому, что я публиковал выше - костыль:

Если так:

C++
1
2
3
4
5
6
7
8
9
    cout << 0 << ' ';
    for (int i = 1; i < n; ++i)
    {
        vector<int> path;
        for (int v = i; v != s; v = p[v])
        path.push_back(v);
        if (find(path.cbegin(), path.cend(), 1) == path.cend()) cout << -1; else cout << path.size();
        cout << ' ';
    }

то тест по условию проходит, а на все другие тесты - неверный ответ.
Например:

Кликните здесь для просмотра всего текста

Input
158 0

Output
0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Correct
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Во второй позиции программа выводит "1", а нужно "-1".
Тоесть, во всех тестах где второе число ноль (например: а) 154 0; б) 680 0; ) программа на второй позиции выводит "1" а надо "-1".

@ReDoX · 05.03.2019, 17:06

aassii, нумерация в графе же с нуля

C++
1
find(path.cbegin(), path.cend(), 0) == path.cend()

Если не сработает, проверьте костыль с компонентами связности

Добавлено через 1 минуту
А, тогда вообще не работает, значит, пробуйте другой костыль

@aassii · 05.03.2019, 20:59 **[ТС]**

Сообщение от ReDoX

Если со всеми костылями не работает, то можно решить в лоб - поиск в ширину. На емаксе есть сам алгоритм и то, как получить кратчайший путь, но по времени это будет очень неэффективно

ReDoX, вы правы.
Сделал правильно через bfs но тайм лимит на половине тестов (>0.250). Как оптимизировать?

Кликните здесь для просмотра всего текста

C++
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
#define _ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int i, j, n, m;
vector<vector<int> > g;
vector<int> dist;
void bfs(int start)
{
    dist = vector<int>(n+1,-1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        for(int to = 1; to <= n; to++)
        if (g[v][to] && dist[to] == -1)
        {
            q.push(to);
            dist[to] = dist[v] + 1;
        }
    }
}
int main(void)
{_
    cin >> n >> m;
    g.resize(n+1);
    for(i = 1; i <= n; i++)
    {
        g[i].resize(n+1);
    }
    for(i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    for(i = 1; i <= n; i++)
    {
        bfs(1);
        if (dist[i] < 0) dist[i] = -1; cout << dist[i] << " ";
    }
    cout << endl;
    return 0;
}

@ReDoX · 05.03.2019, 21:53

Сообщение от aassii

Как оптимизировать?

Никак.

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

Потестите итоговый код:

C++
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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max();
int main() {
  int n;
  int m;
  cin >> n >> m;
 
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int from;
    int to;
    cin >> from >> to;
 
    --from;
    --to;
 
    g[from].push_back({to, 1});
    g[to].push_back({from, 1});
  }
 
  int s = 0;
  vector<int> d(n, INF);
  vector<int> p(n);
 
  d[s] = 0;
 
  vector<char> u(n);
  for (int i = 0; i < n; ++i) {
    int v = -1;
 
    for (int j = 0; j < n; ++j) {
      if (!u[j] && (v == -1 || d[j] < d[v]))
        v = j;
    }
 
    if (d[v] == INF)
      break;
 
    u[v] = true;
 
    for (size_t j = 0; j < g[v].size(); ++j) {
      int to = g[v][j].first, len = g[v][j].second;
      if (d[v] + len < d[to]) {
        d[to] = d[v] + len;
        p[to] = v;
      }
    }
  }
 
  for (int i = 0; i < n; ++i)
    cout << (d[i] == INF ? -1 : d[i]) << ' ';
}

Добавлено через 17 минут
Попробуйте еще это:

C++
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
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long int
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
 
  int n;
  int m;
  cin >> n >> m;
 
  vector<list<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int from;
    int to;
    cin >> from >> to;
 
    --from;
    --to;
 
    g[from].push_back({to, 1});
    g[to].push_back({from, 1});
  }
 
  int start = 0;
  vector<int> distance(n, numeric_limits<int>::max());
 
  distance[start] = 0;
 
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>> pq;
 
  pq.push({0, start});
 
  while (!pq.empty()) {
    int cur = pq.top().second;
 
    pq.pop();
 
    for (const auto& i : g[cur]) {
      int label = i.first;
      int weight = i.second;
 
      if (distance[label] > distance[cur] + weight) {
        distance[label] = distance[cur] + weight;
 
        pq.push({distance[label], label});
      }
    }
  }
 
  for (const auto& i : distance)
    cout << (i == numeric_limits<int>::max() ? -1 : i) << ' ';
}

Как восстановить пути - не знаю

@aassii · 05.03.2019, 22:08 **[ТС]**

Сообщение от ReDoX

Потестите итоговый код:

Первый вариант не проходит по времени 6 тестов (даже с отключением синхронизации между потоками).

@ReDoX · 05.03.2019, 22:23

Сообщение от aassii

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

Попробуйте второй.

Восстановление путей (оставлю это здесь, чтобы потом ссылаться на эту тему):

C++
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
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long int
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
 
  int n;
  int m;
  cin >> n >> m;
 
  vector<list<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int from;
    int to;
    cin >> from >> to;
 
    --from;
    --to;
 
    g[from].push_back({to, 1});
    g[to].push_back({from, 1});
  }
 
  int start = 0;
  vector<int> distance(n, numeric_limits<int>::max());
  vector<int> paths(n);
 
  distance[start] = 0;
 
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;
 
  pq.push({0, start});
 
  while (!pq.empty()) {
    int cur = pq.top().second;
 
    pq.pop();
 
    for (const auto& i : g[cur]) {
      int label = i.first;
      int weight = i.second;
 
      if (distance[label] > distance[cur] + weight) {
        distance[label] = distance[cur] + weight;
 
        paths[label] = cur;
 
        pq.push({distance[label], label});
      }
    }
  }
 
  // Восстановление путей
  //  for (int i = 0; i < n; ++i) {
  //    if (distance[i] != numeric_limits<int>::max()) {
  //      vector<int> path;
  //      for (int v = i; v != start; v = paths[v])
  //        path.emplace_back(v);
  //
  //      path.emplace_back(start);
  //
  //      copy(path.crbegin(), path.crend(), ostream_iterator<int>(cout, " "));
  //    } else {
  //      cout << -1;
  //    }
  //
  //    cout << '\n';
  //  }
 
  cout << '\n';
 
  for (const auto& i : distance)
    cout << (i == numeric_limits<int>::max() ? -1 : i) << ' ';
}

Добавлено через 6 минут
Второй вариант работает ~100ms при ограничениях $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{5}$ (кол-во вершин и ребер) (при решении этой задачи)

@aassii · 06.03.2019, 00:21 **[ТС]**

Сообщение от ReDoX

Второй вариант работает ~100ms при ограничениях (кол-во вершин и ребер)

При отключенной синхронизации между потоками ввода-вывода <0.040.
ReDoX, огромное спасибо за помощь! ))

Добавлено через 48 секунд
За счет чего выиграш по времени?

Добавлено через 5 минут
Просто интересно, можно ли в моем коде както избавиться от этого цикла:

C++
1
2
3
4
    for(i = 1; i <= n; i++)
    {
        g[i].resize(n+1);
    }

объединив его с другим циклом, чтобы уменьшить количество итераций?

@ReDoX · 06.03.2019, 00:47

Сообщение от aassii

За счет чего выиграш по времени?

В оригинальном решении асимптотика примерно $https://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{2} + m)$ (цикл в цикле + проход по ребрам), в измененном примерно $https://www.cyberforum.ru/cgi-bin/latex.cgi?n\log n + m$ (priority_queue:: push работает за логаритм). В первом варианте мы, вроде, подготавливаем все доступные из данной вершины вершины, а потом только работаем с ними; во втором варианте же мы можем получать сразу наиболее выгодное ребро за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(1)$

Сообщение от aassii

Просто интересно, можно ли в моем коде както избавиться от этого цикла:

Скиньте весь код, а там посмотрим (с последними изменениями, то есть тот, который проходит тесты по времени)

@aassii · 06.03.2019, 01:12 **[ТС]**

Сообщение от ReDoX

Скиньте весь код, а там посмотрим (с последними изменениями, то есть тот, который проходит тесты по времени)

Вот скидываю еще раз код, но он не проходит по времени.

C++
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
#define _ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int i, j, n, m;
vector<vector<int> > g;
vector<int> dist;
void bfs(int start)
{
    dist = vector<int>(n+1,-1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        for(int to = 1; to <= n; to++)
        if (g[v][to] && dist[to] == -1)
        {
            q.push(to);
            dist[to] = dist[v] + 1;
        }
    }
}
int main(void)
{_
    cin >> n >> m;
    g.resize(n+1);
    for(i = 1; i <= n; i++)
    {
        g[i].resize(n+1);
    }
    for(i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    for(i = 1; i <= n; i++)
    {
        bfs(1);
        if (dist[i] < 0) dist[i] = -1; cout << dist[i] << " ";
    }
    cout << endl;
    return 0;
}

Просто интересно, можно ли в моем коде както избавиться от этого цикла (строки 27-30):

C++
1
2
3
4
    for(i = 1; i <= n; i++)
    {
        g[i].resize(n+1);
    }

объединив его с другим циклом, чтобы уменьшить количество итераций?

@ReDoX · 06.03.2019, 01:26

Сообщение от aassii

Просто интересно, можно ли в моем коде както избавиться от этого цикла (строки 27-30):

Заранее в конструкторе все сделать (хотя это то же самое):

C++
1
g = vector<vector<int> >(n + 1, vector<int>(n + 1));

Хотя это особо на итоговый результат не повлияет, потому что bfs будет работать примерно за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O({(n + m)}^{n})$ , а костанты, которые присутствуют у вектора при пуше и прочем, на результат особо не повлияют, так как время и так очень большое

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

Города и дороги

Решение

Решение

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240

	Города и дороги 27.02.2019, 19:39. Показов 4347. Ответов 19 Метки нет (Все метки) Семицарство состоит из n городов, занумерованных целыми числами от 1 до n. Столица Семицарства - Король-Берег, и она имеет номер 1. Города Семицарства соединены m двусторонними дорогами длины 1, причем между каждой парой городов не может быть больше 2-х дорог, и ни одна дорога не может соединять город с самим собой. От вас требуется найти расстояния до всех городов от города с номером 1, или сказать, что добраться до него дорогами невозможно. Входные данные: В первой строке входного файла содержатся 2 целые числа n и m (1<=n<=10^5, 0<=m<=min(10^5, n(n-1)/2)) - количество городов и количество дорог между ними. В следующих m строках содержатся по 2 целые числа u, v в каждом (1 ≤ u, v ≤ n, u ≠ v), что означает, что мост u i v соединены двусторонней дорогой. Исходные данные: В единственной строке выведите n чисел di (- 1 ≤ di ≤ n - 1) - расстояние от города с номером один в города с номером i, или -1, если добраться до города дорогами невозможно. Пример: Кликните здесь для просмотра всего текста Ввод 8 8 1 2 2 3 3 4 2 4 5 7 6 7 6 8 5 8 Вывод 0 1 2 2 -1 -1 -1 -1 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	02.03.2019, 00:23 [ТС]
	В моем програмном коде выводится мусор, потому, что после инициализации вектора я не обнулил все его елементы. Как это можно сделать? (например через memset) 0