2025.08.30 京东笔试题

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    int s, e, A, B;
    cin >> s >> e >> A >> B;

    const long long INF = (long long)1e15;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++)
        d[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w < d[u][v]) {
            d[u][v] = w;
            d[v][u] = w; // 无向边
        }
    }

    // 索道 0 费用
    d[A][B] = d[B][A] = 0;

    // Floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (d[i][k] == INF)
                continue;
            for (int j = 1; j <= n; j++) {
                long long v = d[i][k] + d[k][j];
                if (v < d[i][j])
                    d[i][j] = v;
            }
        }
    }

    cout << d[s][e] << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // (distance, node)

void dijkstra(int start, vector<vector<pii>>& graph, vector<int>& dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d != dist[u]) continue;
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    
    vector<vector<pii>> graph(n+1);
    for (int i = 0; i < m; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        graph[u].push_back({v, t});
        graph[v].push_back({u, t});
    }
    
    // 添加特殊索道：A和B之间双向0成本
    graph[A].push_back({B, 0});
    graph[B].push_back({A, 0});
    
    vector<int> dist;
    dijkstra(S, graph, dist);
    
    cout << dist[T] << endl;
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int N = 200005;

int n;
int a[N];
int dp[N], dp_rev[N];
ll cnt[N], cnt_rev[N];

struct Fenw {
    int len;
    vector<int> max_val;
    vector<ll> cnt_val;
    
    Fenw(int n) : len(n), max_val(n + 1, 0), cnt_val(n + 1, 0) {}
    
    void update(int i, int val, ll c) {
        for (; i <= len; i += i & -i) {
            if (val > max_val[i]) {
                max_val[i] = val;
                cnt_val[i] = c;
            } else if (val == max_val[i]) {
                cnt_val[i] = (cnt_val[i] + c) % MOD;
            }
        }
    }
    
    pair<int, ll> query(int i) {
        int res_val = 0;
        ll res_cnt = 0;
        for (; i > 0; i -= i & -i) {
            if (max_val[i] > res_val) {
                res_val = max_val[i];
                res_cnt = cnt_val[i];
            } else if (max_val[i] == res_val) {
                res_cnt = (res_cnt + cnt_val[i]) % MOD;
            }
        }
        return {res_val, res_cnt};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    Fenw fenw(n);
    for (int i = 1; i <= n; i++) {
        auto [val, c] = fenw.query(a[i] - 1);
        dp[i] = val + 1;
        cnt[i] = max(1LL, c);
        fenw.update(a[i], dp[i], cnt[i]);
    }
    
    int LIS = 0;
    for (int i = 1; i <= n; i++) LIS = max(LIS, dp[i]);
    
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) a[i] = n - a[i] + 1;
    
    Fenw fenw_rev(n);
    for (int i = 1; i <= n; i++) {
        auto [val, c] = fenw_rev.query(a[i] - 1);
        dp_rev[i] = val + 1;
        cnt_rev[i] = max(1LL, c);
        fenw_rev.update(a[i], dp_rev[i], cnt_rev[i]);
    }
    
    reverse(dp_rev + 1, dp_rev + n + 1);
    reverse(cnt_rev + 1, cnt_rev + n + 1);
    
    vector<ll> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (dp[i] + dp_rev[i] - 1 == LIS) {
            ans[i] = cnt[i] * cnt_rev[i] % MOD;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}