# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
924526 |
2024-02-09T07:21:33 Z |
crafticat |
Robot (JOI21_ho_t4) |
C++17 |
|
199 ms |
22752 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
constexpr int inf = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<vector<tuple<int,int,int>>> f(n + 1);
for (int i = 0; i < m; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
f[a].emplace_back(c,b,d);
f[b].emplace_back(c,a,d);
}
vector<vector<pii>> g(n + 1);
for (int i = 1; i <= n; ++i) {
map<int, int> app;
for (auto [c, node, d] : f[i]) {
app[c]++;
}
for (auto [c, node, d] : f[i]) {
if (app[c] == 1) g[i].emplace_back(node,0);
else g[i].emplace_back(node,d);
}
}
priority_queue<pii,vector<pii>,greater<>> pq;
pq.emplace(0,1);
vector<int> d(n + 1,inf);
vector<bool> visited(n + 1);
while (!pq.empty()) {
auto [cost, cur] = pq.top();pq.pop();
if (visited[cur]) continue;
d[cur] = cost;
visited[cur] = true;
for (auto [child, len] : g[cur]) {
if (visited[child]) continue;
pq.emplace(len + cost,child);
}
}
cout << d[n];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
8748 KB |
Output is correct |
2 |
Correct |
20 ms |
4328 KB |
Output is correct |
3 |
Correct |
65 ms |
13040 KB |
Output is correct |
4 |
Correct |
29 ms |
6380 KB |
Output is correct |
5 |
Incorrect |
199 ms |
22752 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |