头像

小明同学hh




离线:4个月前


活动打卡代码 AcWing 1123. 铲雪车

#include <iostream>
#include <cmath>
using namespace std;


int main() {
    double x1, x2, y1, y2;
    cin >> x1 >> y1;
    double sum = 0;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        sum += sqrt(dx * dx + dy * dy) * 2;
    }
    int minutes = round(sum / 1000 / 20 * 60);
    int hours = minutes / 60;
    minutes %= 60;

    printf("%d:%02d", hours, minutes);
    return 0;
}


活动打卡代码 AcWing 383. 观光

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;

struct Ver {
    int id, type, dist;
    bool operator > (const Ver &t) const {
        return dist > t.dist;
    }
};
int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N][2], cnt[N][2];
bool st[N][2];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    dist[S][0] = 0, cnt[S][0] = 1;
    priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
    heap.push({S, 0, 0});

    while (heap.size()) {
        Ver t = heap.top();
        heap.pop();

        int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
        if (st[ver][type]) continue;
        st[ver][type] = true;

        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j][0] > distance + w[i]) {
                dist[j][1] = dist[j][0];
                cnt[j][1] = cnt[j][0];
                heap.push({j, 1, dist[j][1]});
                dist[j][0] = distance + w[i];
                cnt[j][0] = count;
                heap.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == distance + w[i]) {
                cnt[j][0] += count;
            }
            else if (dist[j][1] > distance + w[i]) {
                dist[j][1] = distance + w[i];
                cnt[j][1] = count;
                heap.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == distance + w[i]) {
                cnt[j][1] += count;
            }
        }
    }
    int res = cnt[T][0];
    if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
    return res;
}

int main() {
    int cases;
    cin >> cases;
    while (cases -- ) {
        memset(h, -1, sizeof h);
        idx = 0;
        scanf("%d%d", &n, &m);
        while ( m -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &T);
        printf("%d\n", dijkstra());
    }
    return 0;
}



活动打卡代码 AcWing 1134. 最短路计数

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 4e5 + 10;
const int mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx = 0;
int dist[N], cnt[N];
int q[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    cnt[1] = 1;
    int hh = 0, tt = 0;
    q[0] = 1;
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q[ ++ tt ] = j;
            }
            else if (dist[j] == dist[t] + 1) {
                cnt[j] = (cnt[j] + cnt[t]) % mod;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while ( m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    bfs();
    for (int i = 1; i <= n; i ++ ) printf("%d\n", cnt[i]);
    return 0;
}


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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;

int n, m, T;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N], q[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa() {
    int scnt;
    cin >> scnt;
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    int hh = 0, tt = 0;
    while (scnt -- ) {
        int u;
        scanf("%d", &u);
        q[tt ++ ] = u;
        dist[u] = 0;
        st[u] = true;
    }
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
    while (scanf("%d%d%d", &n, &m, &T) != -1) {
        memset(h, -1, sizeof h);
        idx = 0;
        while ( m -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        spfa();
        if (dist[T] == INF) puts("-1");
        else printf("%d\n", dist[T]);
    }
    return 0;
}


活动打卡代码 AcWing 1170. 排队布局

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 10000 + 10000 + 1000 + 10;
const int INF = 0x3f3f3f3f;

int n, m1, m2;
int dist[N];
int h[N], e[M], w[M], ne[M], idx = 0;
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

bool spfa(int size) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 1; i <= size; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
        dist[i] = 0;
    }
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m1 >> m2;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while ( m1 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (b < a) swap(a, b);
        add(a, b, c);
    }
    while ( m2 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (b < a) swap(a, b);
        add(b, a, -c);
    }
    if (spfa(n)) puts("-1");
    else {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }
    return 0;
}


活动打卡代码 AcWing 362. 区间

#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010;
const int M = 150010;

int n;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N];
int q[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa() {
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0, st[0] = true;

    while ( hh != tt ) {
        int t = q[hh ++ ];
        st[t] = false;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
}


int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i < N; i ++ ) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }

    while ( n -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a ++ , b ++ ;
        add(a - 1, b, c);
    }
    spfa();
    cout << dist[50001] << endl;
    return 0;
}


活动打卡代码 AcWing 1169. 糖果

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
typedef long long LL;

int n, m;
int h[N], e[M], ne[M], w[M], idx = 0;
int q[N], cnt[N];
bool st[N];
LL dist[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
/*
bool spfa() {
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0, q[0] = 0;
    st[0] = true;

    while (hh != tt) {
        int t = q[hh ++ ];
        st[t] = false;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j]) {
                    st[j] = true;
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}*/

bool spfa() {
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0, st[0] = true;
    while ( hh != tt ) {
        int t = q[ -- tt ];
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while ( m -- ) {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(a, b, 0), add(b, a, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    for (int i = 1; i <= n; i ++ ) add(0, i, 1);
    if (spfa()) puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}


活动打卡代码 AcWing 1144. 连接格点

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = N * N, K = N * N * 2;

int n, m, k;
int idx[N][N];
struct Edge {
    int a, b, w;
} e[K];
int p[M];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void get_edges() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 01 -1};
    int dw[4] = {1, 2, 1, 2};
    for (int z = 0; z < 2; z ++ ) {
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= m; j ++ ) {
                for (int u = 0; u < 4; u ++ ) {
                    if (u % 2 == z) {
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        if (x && y && x <= n && y <= m) {
                            int a = idx[i][j], b = idx[x][y];
                            if (a < b) e[k ++ ] = {a, b, w};
                        }
                    }
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n * m; i ++ ) p[i] = i;
    for (int i = 1, t = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ , t ++ ) {
            idx[i][j] = t;
        }
    }
    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        int a = idx[x1][y1], b = idx[x2][y2];
        p[find(a)] = find(b);
    }
    get_edges();
    int res = 0;
    for (int i = 0; i < k; i ++ ) {
        int a = find(e[i].a), b = find(e[i].b);
        if (a != b) {
            p[a] = b;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1143. 联络员

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 10010;
const int N = 2010;
struct Edge {
    int a, b, w;
    bool operator < (const Edge &t) const {
        return w < t.w;
    }
}e[M];

int n, m;
int p[N];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0, k = 0;
    while ( m -- ) {
        int t, a, b, w;
        cin >> t >> a >> b >> w;
        if (t == 1) {
            p[find(a)] = find(b);
            res += w;
        }
        else e[k ++ ] = {a, b, w};
    }
    sort(e, e + k);
    for (int i = 0; i < k; i ++ ) {
        int a = find(e[i].a), b = find(e[i].b);
        if (a != b) {
            p[a] = b;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1142. 繁忙的都市

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
const int M = 10010;

int n, m;
struct Edge {
    int a, b, w;
    bool operator < (const Edge &t) const {
        return w < t.w;
    }
} e[M];

int p[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ ) {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; i ++ ) {
        int a = find(e[i].a), b = find(e[i].b);
        if (a != b) {
            p[a] = b;
            res = e[i].w;
        }
    }
    cout << n - 1 << " " << res << endl;
    return 0;
}