# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
934992 |
2024-02-28T10:02:47 Z |
BF001 |
Robot (JOI21_ho_t4) |
C++17 |
|
82 ms |
27876 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define oo 1e18
#define N 100005
#define M 200005
#define fi first
#define se second
typedef pair<int, pair<int, pair<int, int>>> iii;
struct ii
{
int v, c, cst;
};
int n, d[3][N], m, cle[M], u[M], v[M], cl[M], cst[M];
vector<int> adj[N];
map<int, int> sum[N];
void ditra(){
for (int i = 1; i <= n; i++){
d[1][i] = d[0][i] = oo;
}
priority_queue<iii, vector<iii>, greater<iii>> q;
d[1][1] = d[0][1] = 0;
q.push({0, {1, {0, 0}}});
while (!q.empty()){
int du = q.top().fi;
int uu = q.top().se.fi;
int typ = q.top().se.se.se;
int laste = q.top().se.se.fi;
q.pop();
if (du != d[typ][uu]) continue;
//cout << typ << " " << uu << ' ' << d[typ][uu] << "\n";
for (auto x : adj[uu]){
int vv = v[x];
if (vv == uu) vv = u[x];
int clr = cl[x];
int cost = cst[x];
int mi = 0;
if (clr == cl[laste]) mi = cst[laste] * (typ == 1);
int d1 = du + sum[uu][clr] - cost - mi;
//if (uu == 1 && vv == 2) cout << "check : "<< du << " " << sum[uu][clr] << " " << cost << " " << mi << "\n";
if (d1 < d[0][vv]){
d[0][vv] = d1;
q.push({d[0][vv], {vv, {x, 0}}});
}
int d2 = du + cost;
if (typ == 1 && cl[laste] == clr) continue;
if (d2 < d[1][vv]){
d[1][vv] = d2;
q.push({d[1][vv], {vv, {x, 1}}});
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++){
//int u, v, c, cst;
cin >> u[i] >> v[i] >> cl[i] >> cst[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
sum[u[i]][cl[i]] += cst[i];
sum[v[i]][cl[i]] += cst[i];
}
ditra();
int res = min(d[1][n], d[0][n]);
if (res >= oo) cout << -1;
else cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14984 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
24772 KB |
Output is correct |
2 |
Correct |
37 ms |
20056 KB |
Output is correct |
3 |
Incorrect |
82 ms |
27876 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14984 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |