Home 小白月赛56 D(线性筛) F(Dijkstra)
Post
Cancel

小白月赛56 D(线性筛) F(Dijkstra)

D. 阿宁的质数 (线性筛)

1

E. 阿宁去游玩 (Dijkstra / 分层图)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    long long x, y, z;
    cin >> x >> y >> z;

    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        if (a[u] == a[v])
        {
            adj[u].emplace_back(make_pair(v, min(x, z + y)));
            adj[v].emplace_back(make_pair(u, min(x, z + y)));
        } else {
            adj[u].emplace_back(make_pair(v, min(y, z + x)));
            adj[v].emplace_back(make_pair(u, min(y, z + x)));
        }
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    q.emplace(make_pair(0, 1));

    vector<long long> dis(n + 1, 1e18);
    dis[1] = 0;

    while (!q.empty())
    {
        int cur = q.top().second;
        long long d = q.top().first;
        q.pop();

        if (d > dis[cur]) continue;

        if (cur == n)
        {
            cout << d << endl;
            return 0;
        }

        for (auto & e : adj[cur])
        {
            long long w = e.second;
            int v = e.first;

            if (dis[v] > dis[cur] + w)
            {
                dis[v] = dis[cur] + w;
                q.emplace(make_pair(dis[v], v));
            }
        }
    }

    return 0;
}
This post is licensed under CC BY 4.0 by the author.

快速幂

AtCoder Beginner Contest 266 D(DP) E(DP) F(DSU) EX(DP)