# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
806650 |
2023-08-04T08:31:42 Z |
vjudge1 |
Robot (JOI21_ho_t4) |
C++17 |
|
84 ms |
9956 KB |
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100100;
struct edge{
int b, c, p;
};
vector < edge > adj[N];
main() {
#ifdef Home
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Home
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int a, b, c, p; m --> 0;) {
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
}
for(int i = 1; i <= n; ++i) {
sort(adj[i].begin(), adj[i].end(), [&](edge a, edge b) {
return a.c < b.c;
});
}
priority_queue < pair < int, int > > pq;
vector < ll > dist(n + 1, 1e18);
dist[1] = 0;
pq.push({0, 1});
for(; !pq.empty();) {
auto [dst, v] = pq.top();
pq.pop();
if(-dst > dist[v]) {
continue;
}
for(int i = 0; i < adj[v].size(); ++ i) {
int tmp = ((i && adj[v][i - 1].c == adj[v][i].c)||
(i + 1 < adj[v].size() && adj[v][i].c == adj[v][i + 1].c) ? adj[v][i].p : 0);
int u = adj[v][i].b;
if(dist[v] + tmp < dist[u]) {
dist[u] = dist[v] + tmp;
pq.push({-dist[u], u});
}
}
}
cout << (dist[n] == 1e18 ? -1 : dist[n]);
}
Compilation message
Main.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
20 | main() {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < adj[v].size(); ++ i) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | (i + 1 < adj[v].size() && adj[v][i].c == adj[v][i + 1].c) ? adj[v][i].p : 0);
| ~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
6312 KB |
Output is correct |
2 |
Correct |
16 ms |
4308 KB |
Output is correct |
3 |
Correct |
46 ms |
8440 KB |
Output is correct |
4 |
Correct |
23 ms |
5204 KB |
Output is correct |
5 |
Incorrect |
84 ms |
9956 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |