# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
415670 |
2021-06-01T10:56:51 Z |
ruadhan |
Robot (JOI21_ho_t4) |
C++17 |
|
182 ms |
33820 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MX = 1e5 + 5;
struct Edge
{
int u;
int color;
ll price;
};
// vector<pair<int, ll>> adj[MX];
vector<Edge> adj[MX];
int A[MX], B[MX], C[2 * MX];
ll P[2 * MX];
ll dist[MX];
map<int, int> colors[MX];
int N, M;
int main()
{
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> A[i] >> B[i] >> C[i] >> P[i];
adj[A[i]].push_back({B[i], C[i], P[i]});
adj[B[i]].push_back({A[i], C[i], P[i]});
// colors[A[i]].insert(C[i]);
// colors[B[i]].insert(C[i]);
colors[A[i]][C[i]]++;
colors[B[i]][C[i]]++;
}
using T = pair<ll, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 1});
for (int i = 1; i <= N; i++)
dist[i] = LONG_LONG_MAX;
dist[1] = 0;
while (!pq.empty())
{
auto curr = pq.top();
pq.pop();
int v = curr.second;
if (dist[v] < curr.first)
continue;
for (auto e : adj[v])
{
// ll w = (colors[v].find(e.color) == colors[v].end() ? 0 : e.price);
ll w = (colors[v][e.color] == 1 ? 0 : e.price);
if (dist[v] + w < dist[e.u])
{
dist[e.u] = dist[v] + w;
pq.push({dist[e.u], e.u});
}
}
}
if (dist[N] == LONG_LONG_MAX)
cout << -1 << '\n';
else
cout << dist[N] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7372 KB |
Output is correct |
2 |
Correct |
5 ms |
7356 KB |
Output is correct |
3 |
Correct |
5 ms |
7372 KB |
Output is correct |
4 |
Correct |
5 ms |
7348 KB |
Output is correct |
5 |
Correct |
5 ms |
7348 KB |
Output is correct |
6 |
Correct |
5 ms |
7372 KB |
Output is correct |
7 |
Incorrect |
6 ms |
7488 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
16744 KB |
Output is correct |
2 |
Correct |
71 ms |
12380 KB |
Output is correct |
3 |
Runtime error |
174 ms |
33820 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7372 KB |
Output is correct |
2 |
Correct |
5 ms |
7356 KB |
Output is correct |
3 |
Correct |
5 ms |
7372 KB |
Output is correct |
4 |
Correct |
5 ms |
7348 KB |
Output is correct |
5 |
Correct |
5 ms |
7348 KB |
Output is correct |
6 |
Correct |
5 ms |
7372 KB |
Output is correct |
7 |
Incorrect |
6 ms |
7488 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |