头像

bjq

江苏省天一中学少年部




离线:2小时前


最近来访(15)
用户头像
Magneto
用户头像
Jocelin
用户头像
Self.
用户头像
青灯
用户头像
寒山拾不得
用户头像
_Crush
用户头像
kkkobe7
用户头像
RHWFY
用户头像
MIisaka
用户头像
wbc-b
用户头像
SalieriR
用户头像
wscj
用户头像
upczzh
用户头像
TOT_Ysir

活动打卡代码 AcWing 1137. 选择最佳线路

bjq
4天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 1010, M = 21010;
const int INF = 0x3f3f3f3f;
int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool vis[N];

inline void add(int x, int y, int z) {
    e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}

inline void dijkstra(int node) {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, node});
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    d[node] = 0;
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = h[x]; i; i = ne[i]) {
            int y = e[i], z = w[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({d[y], y});
            }
        }
    }
}

int main() {
    while (cin >> n >> m >> T) {
        memset(h, 0, sizeof(h));
        idx = 0;
        while (m--) {
            int x, y, z;
            cin >> x >> y >> z;
            add(x, y, z);
        }
        int s;
        cin >> s;
        while (s--) {
            int ver;
            cin >> ver;
            add(0, ver, 0);
        }
        dijkstra(0);
        if (d[T] == INF) puts("-1");
        else cout << d[T] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

bjq
4天前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2000010;
int n, m, price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool vis[N];

inline void add(int *h, int x, int y) {
    e[++idx] = y, ne[idx] = h[x], h[x] = idx;
}

inline void spfa(int *d, int st, int *h, bool flag) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    if (flag) memset(d, 0x3f, sizeof(dmin));
    q.push(st);
    vis[st] = 1;
    d[st] = price[st];
    while (!q.empty()) {
        int x = q.front(); q.pop();
        vis[x] = 0;
        for (int i = h[x]; i; i = ne[i]) {
            int y = e[i];
            if (flag && d[y] > min(d[x], price[y]) || !flag && d[y] < max(d[x], price[y])) {
                if (flag) d[y] = min(d[x], price[y]);
                else d[y] = max(d[x], price[y]);
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> price[i];
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(h, x, y), add(rh, y, x);
        if (z == 2) add(h, y, x), add(rh, x, y);
    }
    spfa(dmin, 1, h, 1);
    spfa(dmax, n, rh, 0);

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dmax[i] - dmin[i]);
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 342. 道路与航线

bjq
24天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 25010, M = 150010;
const int INF = 0x3f3f3f3f;
int n, mr, mp, s;
struct edge {
    int y, z, ne;
} e[M];
int head[N], idx, id[N], d[N], bcnt, din[N];
vector<int> block[N];
bool vis[N];
queue<int> tq;

inline void add(int x, int y, int z) {
    e[++idx] = {y, z, head[x]};
    head[x] = idx;
}

inline void dfs(int x, int bid) {
    id[x] = bid;
    block[bid].push_back(x);
    for (int i = head[x]; i; i = e[i].ne) {
        int y = e[i].y;
        if (!id[y]) dfs(y, bid);
    }
}

inline void dijkstra(int bid) {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    for (int i = 0; i < block[bid].size(); i++)
        q.push({d[block[bid][i]], block[bid][i]});
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].ne) {
            int y = e[i].y, z = e[i].z;
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (id[y] == id[x]) 
                    q.push({d[y], y});
            } 
            if (id[y] != id[x] && --din[id[y]] == 0)
                tq.push(id[y]);
        }
    }
}

inline void toposort() {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    for (int i = 1; i <= bcnt; i++)
        if (!din[i])
            tq.push(i);
    while (!tq.empty()) {
        int u = tq.front(); tq.pop();
        dijkstra(u);
    }
}

int main() {
    cin >> n >> mr >> mp >> s;
    while (mr--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    for (int i = 1; i <= n; i++)
        if (!id[i]) 
            dfs(i, ++bcnt);
    while (mp--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        din[id[y]]++;
    }
    toposort();
    for (int i = 1; i <= n; i++) 
        if (d[i] > INF / 2) puts("NO PATH");
        else cout << d[i] << endl;

    return 0;
}



活动打卡代码 AcWing 340. 通信线路

bjq
25天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 200010;
int n, m, k;
struct edge {
    int y, z, ne;
} e[M];
int head[N], idx, d[N];
deque<int> q;
bool vis[N];

inline void add(int x, int y, int z) {
    e[++idx] = {y, z, head[x]};
    head[x] = idx;
}

// BFS 01最短路 
bool dijkstra(int maxw) {
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    q.push_back(1);
    d[1] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop_front();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].ne) {
            int y = e[i].y, z = (e[i].z > maxw);
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (z) q.push_back(y);
                else q.push_front(y);
            }
        }
    }
    return d[n] <= k;
}

int main() {
    cin >> n >> m >> k;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z); add(y, x, z);
    }   
    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (dijkstra(mid)) r = mid;
        else l = mid + 1;
    }
    if (r == 1e6 + 1) puts("-1");
    else cout << r << endl;

    return 0;
}



活动打卡代码 AcWing 1135. 新年好

bjq
1个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 100010, M = 200010;
int h[N], e[M], ne[M], w[M], idx, n, m;
bool vis[N];
int d[6][N];
PII p[6];

inline void add(int x, int y, int z) {
    e[++idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
}

inline void dijkstra(int id) {
    memset(vis, 0, sizeof(vis));
    memset(d[id], 0x3f, sizeof(d[id]));
    int node = p[id].second;
    d[id][node] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, node});
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = h[x]; i; i = ne[i]) {
            int y = e[i], z = w[i];
            if (d[id][y] > d[id][x] + z) {
                d[id][y] = d[id][x] + z;
                q.push({d[id][y], y});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    p[0] = {0, 1};
    for (int i = 1, pos; i < 6; i++) {
        cin >> pos;
        p[i] = {i, pos};
    }
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z); add(y, x, z);
    }
    for (int i = 0; i < 6; i++)
        dijkstra(i);
    int ans = 0x3f3f3f3f;
    do {
        int res = 0;
        for (int i = 0; i < 5; i++)
            res += d[p[i].first][p[i + 1].second];
        ans = min(ans, res);
    } while (next_permutation(p + 1, p + 6));
    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 903. 昂贵的聘礼

bjq
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N][N], lv[N];
int d[N];
bool vis[N];

inline int dijkstra(int minlv, int maxlv) {
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[0] = 0;
    for (int i = 1; i <= n + 1; i++) {
        int t = -1;
        for (int j = 0; j <= n; j++)
            if (!vis[j] && (t == -1 || d[t] > d[j]))
                t = j;
        vis[t] = 1;
        for (int j = 1; j <= n; j++)
            if (lv[j] >= minlv && lv[j] <= maxlv)
                d[j] = min(d[j], d[t] + w[t][j]);
    }
    return d[1];
}

int main() {
    cin >> m >> n;
    memset(w, 0x3f, sizeof(w));
    for (int i = 1; i <= n; i++)
        w[i][i] = 0;
    for (int i = 1; i <= n; i++) {
        int price, cnt;
        cin >> price >> lv[i] >> cnt;
        w[0][i] = min(price, w[0][i]);
        while (cnt--) {
            int id, cost;
            cin >> id >> cost;
            w[id][i] = min(w[id][i], cost);
        }
    }
    int res = INF;
    for (int i = lv[1] - m; i <= lv[i]; i++) 
        res = min(res, dijkstra(i, i + m));
    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 2568. 树链剖分

bjq
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010, M = N << 1;
int h[N], e[M], ne[M], w[M], idx, n, m;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct tree {
    int l, r;
    ll add, sum;
} tr[N << 2];

inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }

inline void add(int x, int y) {
    e[++idx] = y, ne[idx] = h[x], h[x] = idx;
}

inline void dfs1(int x, int f, int d) {
    dep[x] = d, fa[x] = f, sz[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == f) continue;
        dfs1(y, x, d + 1);
        sz[x] += sz[y];
        if (sz[son[x]] < sz[y]) 
            son[x] = y;
    }
}

inline void dfs2(int x, int t) {
    id[x] = ++cnt, nw[cnt] = w[x], top[x] = t;
    if (!son[x]) return;
    dfs2(son[x], t);
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}

inline void pushup(int x) {
    tr[x].sum = tr[lc(x)].sum + tr[rc(x)].sum;
}

inline void pushdown(int x) {
    ll &v = tr[x].add;
    if (v) {
        tr[lc(x)].add += v;
        tr[rc(x)].add += v;
        tr[lc(x)].sum += (tr[lc(x)].r - tr[lc(x)].l + 1) * v;
        tr[rc(x)].sum += (tr[rc(x)].r - tr[rc(x)].l + 1) * v;
        v = 0;
    }
}

inline void build(int x, int l, int r) {
    tr[x] = {l, r, 0, nw[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(lc(x), l, mid);
    build(rc(x), mid + 1, r);
    pushup(x);
}

inline void update(int x, int l, int r, ll v) {
    if (l <= tr[x].l && tr[x].r <= r) {
        tr[x].add += v;
        tr[x].sum += v * (tr[x].r - tr[x].l + 1);
        return;
    }
    pushdown(x);
    int mid = tr[x].l  + tr[x].r >> 1;
    if (l <= mid) update(lc(x), l, r, v);
    if (r > mid) update(rc(x), l, r, v);
    pushup(x);
}

inline ll query(int x, int l, int r) {
    if (l <= tr[x].l && tr[x].r <= r) 
        return tr[x].sum;
    pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    ll res = 0;
    if (l <= mid) res += query(lc(x), l, r);
    if (r > mid) res += query(rc(x), l, r);
    return res;
}

inline void update_path(int x, int y, ll v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    update(1, id[y], id[x], v);
}

inline ll query_path(int x, int y) {
    ll res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query(1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    res += query(1, id[y], id[x]);
    return res;
}

inline void update_tree(int x, ll v) {
    update(1, id[x], id[x] + sz[x] - 1, v);
}

inline ll query_tree(int x) {
    return query(1, id[x], id[x] + sz[x] - 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y); add(y, x);
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> m;
    while (m--) {
        int op, u, v; ll k;
        cin >> op >> u;
        if (op == 1) {
            cin >> v >> k;
            update_path(u, v, k);
        } else if (op == 2) {
            cin >> k;
            update_tree(u, k);
        } else if (op == 3) {
            cin >> v;
            cout << query_path(u, v) << endl;
        } else cout << query_tree(u) << endl;
    }

    return 0;
}



活动打卡代码 AcWing 3267. 小明上学

bjq
4个月前
#include <bits/stdc++.h>
using namespace std;

int main() {
    int r, y, g;
    int n, res = 0;
    cin >> r >> y >> g >> n;
    while (n--) {
        int k, t;
        cin >> k >> t;
        if (!k) res += t;
        else if (k == 1) res += t;
        else if (k == 2) res += t + r;
    }
    cout << res << endl;


    return 0;
}



活动打卡代码 LeetCode 92. 反转链表 II

bjq
4个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto a = dummy;
        for (int i = 0; i < left - 1; i++) a = a->next;
        auto b = a->next, c = b->next;
        for (int i = 0; i < right - left; i++) {
            auto d = c->next;
            c->next = b;
            b = c, c = d;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};


活动打卡代码 AcWing 35. 反转链表

bjq
4个月前

Plan A

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto a = head, b =a->next;
        while (b) {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        head->next = NULL;
        return a;
    }
};

Plan B

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};