6105 | 2023. 10. 30 08:03:06 | Gervid | Nagysebességű vasút | cpp17 | Időlimit túllépés 0/100 | 2.099s | 1046908 KiB |
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <limits.h>
using namespace std;
int main()
{
int n, m, i, j, temp1, temp2;
cin >> n >> m;
vector<vector<int>> connections(n, vector<int>(n, -1));
vector<vector<bool>> inoptpath(n, vector<bool>(n, 0));
vector<vector<int>> last(2, vector<int>(n));
last[0][0] = -1, last[1][n-1] = -1;
for (i = 0; i < m; i++)
{
cin >> temp1 >> temp2;
cin >> connections[temp1][temp2];
connections[temp2][temp1] = connections[temp1][temp2];
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> steps;
vector<vector<int>> distance(2, vector<int>(n, INT_MAX));
distance[0][0] = 0, distance[1][n-1] = 0;
int starts[2] = { 0, n - 1 };
for (i = 0; i < 2; i++)
{
steps.push({ 0, starts[i] });
while (steps.size() > 0)
{
for (j = 0; j < n; j++)
{
if (connections[steps.top().second][j] != -1 && distance[i][j] > steps.top().first + connections[j][steps.top().second])
{
distance[i][j] = (steps.top().first + connections[steps.top().second][j]);
steps.push({steps.top().first + connections[steps.top().second][j], j});
last[i][j] = steps.top().second;
}
}
steps.pop();
}
}
temp1 = n - 1;
while (last[0][temp1] != -1)
{
inoptpath[temp1][last[0][temp1]] = true, inoptpath[last[0][temp1]][temp1] = true;
temp1 = last[0][temp1];
}
int opt = distance[0][n - 1];
int min, mini;
set<int> nope;
while (true)
{
min = INT_MAX;
for (i = 1; i < n-1; i++)
{
if (distance[0][i] + distance[1][i] != opt && min > distance[0][i] + distance[1][i] && !nope.count(i))
{
min = distance[0][i] + distance[1][i];
mini = i;
}
}
if (min == INT_MAX)
{
cout << -1;
return 0;
}
int maxreduction = 0;
for (i = 0; i < 2; i++)
{
temp1 = mini;
while (last[i][temp1] != -1)
{
if (inoptpath[temp1][last[i][temp1]])
{
temp1 = last[i][temp1];
continue;
}
if (maxreduction < connections[temp1][last[i][temp1]] - 1)
{
maxreduction = connections[temp1][last[i][temp1]] - 1;
if (maxreduction > distance[0][mini] + distance[1][mini] - opt)
{
cout << distance[0][mini] + distance[1][mini] - opt + 1;
return 0;
}
}
temp1 = last[i][temp1];
}
}
nope.insert(mini);
}
}
//10 13
//0 1 60
//0 2 20
//1 2 5
//1 3 6
//1 4 8
//2 5 20
//3 6 36
//4 7 12
//5 7 20
//5 8 20
//6 9 40
//7 9 20
//8 9 35
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 2088 KiB | ||||
2 | Elfogadva | 3ms | 2220 KiB | ||||
subtask2 | 0/35 | ||||||
3 | Időlimit túllépés | 2.099s | 5964 KiB | ||||
4 | Időlimit túllépés | 2.069s | 6140 KiB | ||||
5 | Időlimit túllépés | 2.04s | 2564 KiB | ||||
6 | Hibás válasz | 23ms | 11724 KiB | ||||
7 | Hibás válasz | 10ms | 6556 KiB | ||||
8 | Hibás válasz | 13ms | 12060 KiB | ||||
subtask3 | 0/30 | ||||||
9 | Futási hiba | 423ms | 1046908 KiB | ||||
10 | Futási hiba | 354ms | 1046660 KiB | ||||
11 | Futási hiba | 340ms | 1046596 KiB | ||||
12 | Futási hiba | 342ms | 1046620 KiB | ||||
13 | Futási hiba | 423ms | 1046592 KiB | ||||
14 | Futási hiba | 340ms | 1046580 KiB | ||||
subtask4 | 0/35 | ||||||
15 | Futási hiba | 414ms | 1046332 KiB | ||||
16 | Futási hiba | 340ms | 1046316 KiB | ||||
17 | Futási hiba | 423ms | 1046084 KiB | ||||
18 | Futási hiba | 340ms | 1046060 KiB | ||||
19 | Futási hiba | 425ms | 1045916 KiB | ||||
20 | Futási hiba | 423ms | 1045908 KiB | ||||
21 | Futási hiba | 386ms | 1045676 KiB | ||||
22 | Futási hiba | 340ms | 1045668 KiB | ||||
23 | Futási hiba | 342ms | 1045572 KiB | ||||
24 | Futási hiba | 342ms | 1045568 KiB | ||||
25 | Futási hiba | 340ms | 1045340 KiB | ||||
26 | Futási hiba | 421ms | 1045344 KiB | ||||
27 | Futási hiba | 419ms | 1045152 KiB |