Всем доброго времени суток! Есть такая задача.
Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.
Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.
Входные данные
Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10^4, 2≤k≤10^4). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −10^5≤wi≤10^5). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.
Выходные данные
Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.
Примеры
входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
выходные данные
6
5 6 5 7 2 3
входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
выходные данные
infinitely kind
Вот мой код к этой программе
Код:
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int ret(vector<vector<int>>& from, int u, int v, vector<int>& path)
{
if (u == v)
{
return 0;
}
if (from[u][v] == u || from[u][v] == v)
{
path.push_back(v);
return 0;
}
ret(from, u, from[u][v], path);
ret(from, from[u][v], v, path);
return 0;
}
int main()
{
const int inf = -1e9;
bool cycle = false;
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> graph(n, vector<int>(n, inf)), from(n, vector<int>(n, -1));
vector<int> a(k + 1, 0), path, ans;
map<pair<int, int>, int> flights;
path.push_back(0);
for (int i = 0; i < m; i++)
{
int b, e, w;
cin >> b >> e >> w;
b--, e--;
graph[b][e] = w;
flights[{b, e}] = i;
from[b][e] = b;
}
for (int i = 1; i <= k; i++)
{
cin >> a[i];
a[i]--;
}
for (int i = 0; i < n; i++)
{
graph[i][i] = 0;
}
for (int K = 0; K < n; K++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (graph[i][j] < graph[i][K] + graph[K][j])
{
graph[i][j] = graph[i][K] + graph[K][j];
from[i][j] = K;
}
}
}
}
for (int i = 0; i <= k; i++)
{
if (graph[a[i]][a[i]] > 0)
{
cycle = true;
}
}
if (cycle)
{
cout << "infinitely kind";
}
else
{
for (int j = 1; j <= k; j++)
{
ret(from, a[j - 1], a[j], path);
}
for (int i = 1; i < path.size(); i++)
{
ans.push_back(flights[{path[i - 1], path[i]}] + 1);
}
cout << ans.size() << endl;
for (auto el : ans)
{
cout << el << " ";
}
}
}
Но дело в том, что на информатиксе он проходит 11 тестов из 24. Помогите, пожалуйста, разобраться, где я допустил ошибку. Скорее всего, проблема таится где-то в функции, потому что все случаи с циклом программа проходит корректно.
P. s.
Некоторые уточнения насчет условия
1) Города, в которых надо дать концерт, нужно посетить в том порядке, в котором они вбиты
2) Можно посещать города по несколько раз. Это относится и к выбранным
3) Допустим, мы посетили А[j - 1] город и нам нужно теперь посетить город A[j], если мы туда попадаем, то концерт нужно будет провести
4) Можно заехать в выбранный город, после того как дали в нем концерт
22.11.2020, 13:22 