Submission #1260707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260707		khoile08	Robot (JOI21_ho_t4)	C++17	34 / 100	3097 ms	42204 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 2e5 + 5;

int n, m;
struct Adj1 {
    int v, c, p;
};
vector<Adj1> tg[N];
struct Adj2 {
    int v;
    ll w1, w2;
    int c;
};
vector<Adj2> g[N];
ll sum[M];

struct State {
    ll cost;
    int u, c;

    bool operator < (const State &other) const {return cost > other.cost;}
};
priority_queue<State> pq;
map<int, ll> d[N];

void Solve() {
    FOR(i, 1, n) {
        for(Adj1 H : tg[i]) sum[H.c] += H.p;
        for(Adj1 H : tg[i]) g[i].pb({H.v, sum[H.c] - H.p, H.p, H.c});
        for(Adj1 H : tg[i]) sum[H.c] = 0;
    }
    pq.push({0, 1, 0});
    d[1][0] = 0;
    while(!pq.empty()) {
        ll cost = pq.top().cost;
        int u = pq.top().u;
        int c = pq.top().c;
        pq.pop();
        if(cost != d[u][c]) continue;
        if(c == 0) {
            for(auto H : g[u]) {
                int v = H.v;
                ll w1 = H.w1;
                ll w2 = H.w2;
                int new_c = H.c;
                /// doi mau phan con lai
                if(d[v].count(0) == 0 || d[v][0] > cost + min(w1, w2)) {
                    d[v][0] = cost + min(w1, w2);
                    pq.push({d[v][0], v, 0});
                }
                /// doi mau i
                if(d[v].count(new_c) == 0 || d[v][new_c] > cost) {
                    d[v][new_c] = cost;
                    pq.push({d[v][new_c], v, new_c});
                }
            }
        }
        else {
            for(auto H : g[u]) {
                int v = H.v;
                ll w1 = H.w1;
                ll w2 = H.w2;
                int new_c = H.c;
                if(new_c == c && (d[v].count(0) == 0 || d[v][0] > cost + w1)) {
                    d[v][0] = cost + w1;
                    pq.push({d[v][0], v, 0});
                }
            }
        }
    }
    cout << (d[n].count(0) ? d[n][0] : -1) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n >> m;
        FOR(i, 1, m) {
            int u, v, c, p;
            cin >> u >> v >> c >> p;
            tg[u].pb({v, c, p});
            tg[v].pb({u, c, p});
        }
        Solve();
    }
}

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42