# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
927665 |
2024-02-15T08:28:23 Z |
LonlyR |
Robot (JOI21_ho_t4) |
C++17 |
|
959 ms |
111320 KB |
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int dp[maxn];
vector<array<int, 3>> adj[maxn];
map<int,int> col[maxn];
map<int,ii> dpc[maxn];
map<int,vector<ii>> adjc[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> m;
for (int i = 1, u, v, w, t; i <= m; i++)
{
cin >> u >> v >> w >> t;
adj[u].push_back({v, w, t});
adj[v].push_back({u, w, t});
adjc[u][w].emplace_back(v, t);
adjc[v][w].emplace_back(u, t);
if (col[u].count(w)) col[u][w] = -1;
else col[u][w] = 0;
if (col[v].count(w)) col[v][w] = -1;
else col[v][w] = 0;
}
for (int i = 1; i <= n; i++)
for (auto p : adj[i])
{
int &u = col[i][p[1]];
if (u == 0) continue;
if (u == -1) u = p[2];
else u += p[2];
}
#define iii tuple<int,int,int>
priority_queue<iii, vector<iii>, greater<iii>> pq;
memset(dp, 0x3f, sizeof dp);
int oo = dp[0];
dp[1] = 0;
pq.emplace(0, 1, 0);
while (pq.size())
{
int u, v, w;
tie(v, u, w) = pq.top();
pq.pop();
if (w == 0)
{
if (v != dp[u]) continue;
for (auto p : adj[u])
{
int color = p[1], cost = p[2], nxt = p[0];
if (col[u][color] != 0)
{
int val = v + cost, f = 0;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1;
if (!dpc[nxt].count(color) || dpc[nxt][color].ff > val - cost)
dpc[nxt][color] = {val - cost, u},
pq.emplace(val - cost, nxt, color);
val = v + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1;
if (f) pq.emplace(dp[nxt], nxt, 0);
}
else if (dp[nxt] > v)
dp[nxt] = v,
pq.emplace(dp[nxt], nxt, 0);
}
}
else for (auto p : adjc[u][w])
{
int nxt = p.ff, cost = p.ss, color = w;
if (nxt != dpc[u][color].ss)
{
int val = dpc[u][color].ff + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
pq.emplace(dp[nxt], nxt, 0);
if (!dpc[nxt].count(color) || dpc[nxt][color].ff > val - cost)
dpc[nxt][color] = {val - cost, u},
pq.emplace(val - cost, nxt, color);
}
}
}
cout << (dp[n] == oo ? -1 : dp[n]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
34652 KB |
Output is correct |
2 |
Correct |
7 ms |
34652 KB |
Output is correct |
3 |
Correct |
7 ms |
34908 KB |
Output is correct |
4 |
Correct |
8 ms |
34652 KB |
Output is correct |
5 |
Correct |
7 ms |
34908 KB |
Output is correct |
6 |
Correct |
8 ms |
34652 KB |
Output is correct |
7 |
Correct |
9 ms |
35016 KB |
Output is correct |
8 |
Correct |
10 ms |
34908 KB |
Output is correct |
9 |
Incorrect |
11 ms |
35420 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
59144 KB |
Output is correct |
2 |
Correct |
64 ms |
46732 KB |
Output is correct |
3 |
Correct |
201 ms |
61696 KB |
Output is correct |
4 |
Correct |
120 ms |
50892 KB |
Output is correct |
5 |
Incorrect |
959 ms |
111320 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
34652 KB |
Output is correct |
2 |
Correct |
7 ms |
34652 KB |
Output is correct |
3 |
Correct |
7 ms |
34908 KB |
Output is correct |
4 |
Correct |
8 ms |
34652 KB |
Output is correct |
5 |
Correct |
7 ms |
34908 KB |
Output is correct |
6 |
Correct |
8 ms |
34652 KB |
Output is correct |
7 |
Correct |
9 ms |
35016 KB |
Output is correct |
8 |
Correct |
10 ms |
34908 KB |
Output is correct |
9 |
Incorrect |
11 ms |
35420 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |