Editorial for Bedao Grand Contest 12 - MINDIST


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét chung: ta thấy số ~X~ trong hàm định nghĩa cost có thể bỏ đi và tăng trọng số các cạnh của đồ thị lên ~X~ đơn vị.

Subtask 1: ~1 \leq n, m \leq 10~

Sinh ra tất cả các đường đi có thể trên đồ thị.

Subtask 2: ~1 \leq n, m \leq 100~

Ta có ~f[i][a][b]~ là đường đi có cost nhỏ nhất bắt đầu từ đỉnh ~S~ đến đỉnh ~i~ trên đồ thị và có cạnh max là cạnh thứ ~a~, cạnh min là cạnh thứ ~b~. Xuất phát từ đỉnh ~S~ ta tính các giá trị ~f[i][a][b]~ có thể.

Subtask 3: ~m = n~

Như subtask2 tuy nhiên cặp giá trị ~a,b~ của mỗi đỉnh chỉ có nhiều nhất 2 cặp giá trị.

Subtask 4:

Ta có thể coi việc trừ max và cộng min như việc trừ đi 1 trọng số bất kì và cộng một trọng số bất kì. Nếu đó không phải max và min thì đường đi không bao giờ nhỏ nhất. Do vậy ta áp dụng trực tiếp được thuật toán dijkstra với ~disk[i][mask]~ là đường đi có cost nhỏ nhất từ ~S~ đến ~i~ và ~mask~ thể hiện việc cộng hay trừ chưa.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
template<typename A, typename B> bool minimize(A& a, B b) {
    return a > b? a = b, true : false;
}

const int N = 2e5 + 5;

int n, m, s, c;
vector<pair<int, int>> adj[N];
ll dist[N][4];

void solve() {
    cin >> n >> m >> s >> c;
    for (int i = 1; i <= m; ++ i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    memset(dist, 0x3f, sizeof dist);
    dist[s][0] = 0;
    priority_queue<tuple<ll, int, int>> pq;
    pq.push({0, s, 0});
    while (pq.size()) {
        auto [l, u, mask] = pq.top();
        pq.pop();
        l = -l;
        if (l > dist[u][mask]) continue;
        clog << db(l) << db(u) << db(mask) << endl;
        for (auto [v, w] : adj[u]) {
            if (minimize(dist[v][mask], dist[u][mask] + w + c)) {
                pq.push({-dist[v][mask], v, mask});
            }
            if (!(mask & 1)) {
                if (minimize(dist[v][mask ^ 1], dist[u][mask] + w - w + c)) {
                    pq.push({-dist[v][mask ^ 1], v, mask ^ 1});
                }
            }
            if (!(mask >> 1 & 1)) {
                if (minimize(dist[v][mask ^ 2], dist[u][mask] + w + w + c)) {
                    pq.push({-dist[v][mask ^ 2], v, mask ^ 2});
                }
            }
            if (mask == 0) {
                if (minimize(dist[v][3], dist[u][0] + w + c)) {
                    pq.push({-dist[v][3], v, 3});
                }
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        if (i != s) cout << dist[i][3] << " ";
    }
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    #ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    freopen("main.log", "w", stderr);
    #endif
    solve();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.