# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
770563 |
2023-07-01T13:24:29 Z |
Blagoj |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
2046464 KB |
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
map<int, vector<tuple<int, int, int>>> edg[100005];
unordered_map<int, ll> sum[100005], dp2[100005];
ll dp[100005];
int n, m;
struct T {
ll dist;
int place, color;
};
bool operator < (T a, T b) { return a.dist > b.dist; }
void solve() {
priority_queue<T> pq;
pq.push({0, 1, 0});
while (pq.size() > 0) {
T top = pq.top();
pq.pop();
if (top.color) {
if (top.dist != dp2[top.place][top.color]) continue;
for (auto [to, color, cost] : edg[top.place][top.color]) {
ll newCost = top.dist + sum[top.place][color] - cost;
if (newCost < dp[to]) {
dp[to] = newCost;
pq.push({dp[to], to, 0});
}
}
continue;
}
if (top.dist != dp[top.place]) continue;
for (int i = 0; i < edg[top.place].size(); i++) {
for (auto [to, color, cost] : edg[top.place][i]) {
ll newCost = top.dist + min((ll) cost, sum[top.place][color] - (ll) cost);
if (newCost < dp[to]) {
dp[to] = newCost;
pq.push({dp[to], to, 0});
}
if (!dp2[to].count(color) || top.dist < dp2[to][color]) {
dp2[to][color] = top.dist;
pq.push({dp2[to][color], to, color});
}
}
}
}
cout << ((dp[n] == LLONG_MAX) ? -1 : dp[n]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 2; i <= n; i++) dp[i] = LLONG_MAX;
for (int i = 0; i < m; i++) {
int from, to, color, cost;
cin >> from >> to >> color >> cost;
edg[from][color].push_back({to, color, cost});
edg[to][color].push_back({from, color, cost});
sum[from][color] += cost;
sum[to][color] += cost;
}
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<std::tuple<int, int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < edg[top.place].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
2 |
Correct |
9 ms |
15976 KB |
Output is correct |
3 |
Correct |
10 ms |
15916 KB |
Output is correct |
4 |
Correct |
9 ms |
15924 KB |
Output is correct |
5 |
Correct |
9 ms |
16436 KB |
Output is correct |
6 |
Correct |
9 ms |
15904 KB |
Output is correct |
7 |
Correct |
18 ms |
20428 KB |
Output is correct |
8 |
Correct |
10 ms |
17496 KB |
Output is correct |
9 |
Correct |
136 ms |
93728 KB |
Output is correct |
10 |
Correct |
145 ms |
103408 KB |
Output is correct |
11 |
Correct |
228 ms |
160516 KB |
Output is correct |
12 |
Correct |
29 ms |
28116 KB |
Output is correct |
13 |
Correct |
71 ms |
56136 KB |
Output is correct |
14 |
Correct |
103 ms |
75520 KB |
Output is correct |
15 |
Correct |
38 ms |
34288 KB |
Output is correct |
16 |
Correct |
104 ms |
79180 KB |
Output is correct |
17 |
Correct |
91 ms |
69208 KB |
Output is correct |
18 |
Correct |
9 ms |
16644 KB |
Output is correct |
19 |
Correct |
35 ms |
31544 KB |
Output is correct |
20 |
Correct |
151 ms |
101788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3140 ms |
2046464 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
2 |
Correct |
9 ms |
15976 KB |
Output is correct |
3 |
Correct |
10 ms |
15916 KB |
Output is correct |
4 |
Correct |
9 ms |
15924 KB |
Output is correct |
5 |
Correct |
9 ms |
16436 KB |
Output is correct |
6 |
Correct |
9 ms |
15904 KB |
Output is correct |
7 |
Correct |
18 ms |
20428 KB |
Output is correct |
8 |
Correct |
10 ms |
17496 KB |
Output is correct |
9 |
Correct |
136 ms |
93728 KB |
Output is correct |
10 |
Correct |
145 ms |
103408 KB |
Output is correct |
11 |
Correct |
228 ms |
160516 KB |
Output is correct |
12 |
Correct |
29 ms |
28116 KB |
Output is correct |
13 |
Correct |
71 ms |
56136 KB |
Output is correct |
14 |
Correct |
103 ms |
75520 KB |
Output is correct |
15 |
Correct |
38 ms |
34288 KB |
Output is correct |
16 |
Correct |
104 ms |
79180 KB |
Output is correct |
17 |
Correct |
91 ms |
69208 KB |
Output is correct |
18 |
Correct |
9 ms |
16644 KB |
Output is correct |
19 |
Correct |
35 ms |
31544 KB |
Output is correct |
20 |
Correct |
151 ms |
101788 KB |
Output is correct |
21 |
Execution timed out |
3140 ms |
2046464 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |