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;
}