#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vl = vector<ll>;
const int mx = 5'000;
int N, M;
vi T(mx), L(mx), R(mx), C(mx);
int lw, rw;
vi edge[mx + 2];
vl wt[mx + 2];
void add_edge(int u, int v, ll w)
{
edge[u].push_back(v);
// edge[v].push_back(u); //check this later???
wt[u].push_back(w);
// wt[v].push_back(w);
// cerr << "adding edge " << u << " -> " << v << '\n';
}
ll INF = 1'000'000'000'000'000'000LL;
vl lw_dist(mx+2, INF);
struct pos
{
int i;
};
bool operator < (pos A, pos B)
{
if(lw_dist[A.i] == lw_dist[B.i]) return A.i < B.i;
return lw_dist[A.i] < lw_dist[B.i];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for(int i = 0; i < M; i++)
{
cin >> T[i] >> L[i] >> R[i] >> C[i];
}
lw = M;
rw = M + 1;
for(int i = 0; i < M; i++)
{
for(int j = 0; j < M; j++)
{
if(j == i) continue;
if(L[j] <= R[i] + 1 - abs(T[j] - T[i]) && R[i] + 1 - abs(T[j] - T[i]) <= R[j])
add_edge(i, j, C[i]);
}
}
for(int i = 0; i < M; i++)
{
if(L[i] == 1) add_edge(lw, i, 0);
if(R[i] == N) add_edge(i, rw, C[i]);
}
lw_dist[lw] = 0;
// cerr << "check\n";
set<pos> S;
for(int i = 0; i < M+2; i++) S.insert(pos{i});
while(!S.empty())
{
int u = S.begin()->i;
S.erase(S.begin());
for(int e = 0; e < int(edge[u].size()); e++)
{
int v = edge[u][e];
ll w = wt[u][e];
if(lw_dist[u] + w < lw_dist[v])
{
S.erase(pos{v});
lw_dist[v] = lw_dist[u] + w;
S.insert(pos{v});
}
}
}
if(lw_dist[rw] == INF) lw_dist[rw] = -1;
cout << lw_dist[rw] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
995 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
592 KB |
Output is correct |
2 |
Correct |
1 ms |
592 KB |
Output is correct |
3 |
Correct |
1 ms |
652 KB |
Output is correct |
4 |
Correct |
1 ms |
592 KB |
Output is correct |
5 |
Correct |
1 ms |
592 KB |
Output is correct |
6 |
Correct |
1 ms |
592 KB |
Output is correct |
7 |
Correct |
1 ms |
592 KB |
Output is correct |
8 |
Correct |
1 ms |
592 KB |
Output is correct |
9 |
Correct |
1 ms |
592 KB |
Output is correct |
10 |
Correct |
0 ms |
592 KB |
Output is correct |
11 |
Correct |
0 ms |
592 KB |
Output is correct |
12 |
Correct |
1 ms |
592 KB |
Output is correct |
13 |
Correct |
1 ms |
592 KB |
Output is correct |
14 |
Correct |
1 ms |
592 KB |
Output is correct |
15 |
Correct |
0 ms |
592 KB |
Output is correct |
16 |
Correct |
1 ms |
592 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
18 |
Correct |
1 ms |
592 KB |
Output is correct |
19 |
Correct |
1 ms |
592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
592 KB |
Output is correct |
2 |
Correct |
1 ms |
592 KB |
Output is correct |
3 |
Correct |
1 ms |
652 KB |
Output is correct |
4 |
Correct |
1 ms |
592 KB |
Output is correct |
5 |
Correct |
1 ms |
592 KB |
Output is correct |
6 |
Correct |
1 ms |
592 KB |
Output is correct |
7 |
Correct |
1 ms |
592 KB |
Output is correct |
8 |
Correct |
1 ms |
592 KB |
Output is correct |
9 |
Correct |
1 ms |
592 KB |
Output is correct |
10 |
Correct |
0 ms |
592 KB |
Output is correct |
11 |
Correct |
0 ms |
592 KB |
Output is correct |
12 |
Correct |
1 ms |
592 KB |
Output is correct |
13 |
Correct |
1 ms |
592 KB |
Output is correct |
14 |
Correct |
1 ms |
592 KB |
Output is correct |
15 |
Correct |
0 ms |
592 KB |
Output is correct |
16 |
Correct |
1 ms |
592 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
18 |
Correct |
1 ms |
592 KB |
Output is correct |
19 |
Correct |
1 ms |
592 KB |
Output is correct |
20 |
Correct |
263 ms |
107804 KB |
Output is correct |
21 |
Correct |
264 ms |
108148 KB |
Output is correct |
22 |
Correct |
43 ms |
2056 KB |
Output is correct |
23 |
Correct |
42 ms |
2004 KB |
Output is correct |
24 |
Correct |
127 ms |
53536 KB |
Output is correct |
25 |
Correct |
68 ms |
6728 KB |
Output is correct |
26 |
Correct |
42 ms |
1680 KB |
Output is correct |
27 |
Correct |
40 ms |
1388 KB |
Output is correct |
28 |
Correct |
132 ms |
53620 KB |
Output is correct |
29 |
Correct |
55 ms |
6448 KB |
Output is correct |
30 |
Correct |
42 ms |
1736 KB |
Output is correct |
31 |
Correct |
37 ms |
1172 KB |
Output is correct |
32 |
Correct |
315 ms |
125716 KB |
Output is correct |
33 |
Correct |
297 ms |
176072 KB |
Output is correct |
34 |
Correct |
115 ms |
3116 KB |
Output is correct |
35 |
Correct |
300 ms |
127532 KB |
Output is correct |
36 |
Correct |
298 ms |
176200 KB |
Output is correct |
37 |
Correct |
113 ms |
3032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
995 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |