제출 #1085870

#제출 시각아이디문제언어결과실행 시간메모리
1085870DaciejMaciejRobot (JOI21_ho_t4)C++17
0 / 100
201 ms39100 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld; template <class T> using VV = vector<vector<T>>; using VI = vector<int>; using VVI = vector<vector<int>>; using VL = vector<long long>; using VVL = vector<vector<long long>>; using VC = vector<char>; using VVC = vector<vector<char>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VD = vector<double>; using VVD = vector<vector<double>>; using PII = pair<int, int>; using PLL = pair<long long, long long>; using PIL = pair<int, long long>; using PLI = pair<long long, int>; using VPII = vector<pair<int, int>>; using VPLL = vector<pair<long long, long long>>; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (int(b)); i++) #define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() #define sq(a) ((a) * (a)) #define sz(x) ((int)s.size()) // zero indexed template <class T> struct segtree { const T def = 0; int n; vector<T> seg; segtree(int _size) : n(_size), seg(2 * _size, def) {} T merge(T a, T b) { return max(a, b); } void update(int pos, T val) { for (seg[pos += n] = val; pos /= 2;) { seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]); } } T query(int l, int r) { // get [l, r] T a = def, b = def; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l % 2) a = merge(a, seg[l++]); if (r % 2) b = merge(b, seg[--r]); } return merge(a, b); } }; const ll MOD = 1e9 + 7; template <class T> void maxi(T &a, T b) { a = max(a, b); } template <class T> void mini(T &a, T b) { a = min(a, b); } template <class T> void addi(T &a, T b) { a = (a + b) % MOD; } template <class T> void subi(T &a, T b) { a = (a - b + MOD) % MOD; } template <class T> T add(T a, T b) { return (a + b) % MOD; } template <class T> T sub(T a, T b) { return (a - b + MOD) % MOD; } template <class T> T mul(T a, T b) { return ((a % MOD) * (b % MOD)) % MOD; } ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } struct DSU { VI par; VI size; DSU(int _n) : par(_n), size(_n, 1) { iota(ALL(par), 0); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (size[y] > size[x]) swap(x, y); size[x] += size[y]; par[y] = x; return true; } int find(int x) { return (par[x] == x ? x : par[x] = find(par[x])); } bool connected(int x, int y) { return find(x) == find(y); } void reset() { FOR(i, 0, par.size()) par[i] = i, size[i] = 1; } }; const int INF = 1e9; const int MAX_N = 1e5 + 3; int n, m; struct Edge { int to; int c; ll p; }; struct State { ll cost; int node; int color; Edge backEdge; bool operator>(const State &other) const { return cost > other.cost; } }; vector<Edge> g[MAX_N]; map<int, ll> psum[MAX_N]; VVL dp(MAX_N, VL(2, 1e17)); map<int, ll> dp2[MAX_N]; // 0 - came from unique edge // came from uncolored edge /* TO:DO - fix case1 and case2, beacuse comming from another color might cause better answear so keep just do[node][c] as the minimum of comming to node via edge c */ void solve() { cin >> n >> m; FOR(i, 0, m) { int a, b, c, p; cin >> a >> b >> c >> p; g[a].PB({b, c, p}); g[b].PB({a, c, p}); psum[a][c] += p; psum[b][c] += p; } priority_queue<State, vector<State>, greater<State>> pq; dp[1][0] = 0; pq.push({0, 1, 0, {0, -1, 0}}); while (!pq.empty()) { auto [cost, node, color, back_edge] = pq.top(); //cerr << "cost=" << cost << " nd=" << node << " c=" << color << " dp=" << min(dp[node][0], dp[node][1]) << LINE; pq.pop(); for (auto e : g[node]) { //cerr << "AT e: to=" << e.to << " c=" << e.c << " p=" << e.p << LINE; if (color == 0) { // came from any and repaint rest color e.c ll case1 = cost + psum[node][e.c] - e.p; if(e.c == back_edge.c) case1 -= back_edge.p; //cerr << "case1= " << case1 << LINE; if (!dp2[e.to].count(e.c) || case1 < dp2[e.to][e.c]) { dp[e.to][1] = case1; dp2[e.to][e.c] = case1; pq.push({case1, e.to, e.c, e}); } } else { if (e.c != color) // possibly can pass using e { ll case2 = cost + psum[node][e.c] - e.p; //cerr << "case2= " << case2 << LINE; if (!dp2[e.to].count(e.c) || case2 < dp2[e.to][e.c]) { dp[e.to][1] = case2; dp2[e.to][e.c] = case2; pq.push({case2, e.to, e.c, e}); } } } // universal: just repaint e to unique color ll case3 = cost + e.p; //cerr << "case3= " << case3 << LINE; if (case3 <= dp[e.to][0]) { dp[e.to][0] = case3; pq.push({case3, e.to, 0, e}); } } //cerr << LINE; } ll ans = min(dp[n][0], dp[n][1]); cout << (ans < 1e17 ? ans : -1) << LINE; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...