个人空间 - AcWing

fangy

关注数

粉丝数

阅读量

4116

+关注发消息

离线：3小时前

最近来访(78)

Donlonboy_5

CODE_HUNTER

Chongyu

杰梦舒

荀彧_2

Ferrynan

看到我请叫我早点睡觉

yxc的小迷妹

wcyyyooo

烟森-

Garfy

szn419

摆乱者也

Updater

远峰

三太子敖丙

-浪漫主义狗-

窗外的麻雀

RKTHlr

活动打卡代码 AcWing 178. 第K短路

fangy
4小时前

                #include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 20010;

int n, m, S, T, K;
int rh[N], h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];

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

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    for (int i = 0; i < n - 1; ++i)
    {
        int t = 0;
        for (int i = 1; i <= n; ++i)
            if (!st[i] && dist[i] < dist[t])
                t = i;

        st[t] = true;

        for (int i = rh[t]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = min(dist[j], dist[t] + w[i]);
        }
    }
}

int astar()
{
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S], {0, S}});

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

        int distance = t.y.x, ver = t.y.y;

        cnt[ver]++;
        if (cnt[T] == K) return distance;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            int fj = distance + w[i] + dist[j];
            if (cnt[j] <= K) heap.push({fj, {distance + w[i], j}});
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(rh, b, a, c);
    }

    cin >> S >> T >> K;
    if (S == T) K++;

    dijkstra();

    int t = astar();
    cout << t << endl;

    return 0;
}

            

活动打卡代码 AcWing 178. 第K短路

fangy
4小时前

                #include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 20010;

int n, m, S, T, K;
int rh[N], h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];

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

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    for (int i = 0; i < n - 1; ++i)
    {
        int t = 0;
        for (int i = 1; i <= n; ++i)
            if (!st[i] && dist[i] < dist[t])
                t = i;

        st[t] = true;

        for (int i = rh[t]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = min(dist[j], dist[t] + w[i]);
        }
    }
}

int astar()
{
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S], {0, S}});

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

        int distance = t.y.x, ver = t.y.y;

        cnt[ver]++;
        if (cnt[T] == K) return distance;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            int fj = distance + w[i] + dist[j];
            if (cnt[j] <= K) heap.push({fj, {distance + w[i], j}});
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(rh, b, a, c);
    }

    cin >> S >> T >> K;
    if (S == T) K++;

    dijkstra();

    int t = astar();
    cout << t << endl;

    return 0;
}

            

活动打卡代码 AcWing 859. Kruskal算法求最小生成树（算法基础课）

fangy
7小时前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 2 * N;

int n, m;
int p[N];

struct Edge
{
    int a, b, c;
    bool operator<(const Edge& E)
    {
        return c < E.c;
    }
} edge[M];

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

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }

    sort(edge, edge + m);

    for (int i = 1; i <= n; ++i) p[i] = i;

    int res = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n - 1; ++i)
    {
        auto &t = edge[i];
        int pa = find(t.a), pb = find(t.b);
        if (pa != pb) p[pa] = pb, res += t.c, cnt++;
    }
    if (cnt < n - 1) puts("impossible");
    else cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 858. Prim算法求最小生成树（算法基础课）

fangy
8小时前

                #include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int Prim()
{
    int res = 0;
    for (int k = 0; k < n; ++k)
    {
        int t = -1;
        for (int i = 1; i <= n; ++i)
            if (!st[i] && (t == -1 || dist[i] < dist[t]))
                t = i;

        if (k && dist[t] == INF) return INF;

        st[t] = true;
        if (k) res += dist[t];

        for (int i = 1; i <= n; ++i) dist[i] = min(dist[i], g[t][i]);        
    }
    return res;
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int res = Prim();
    if (res == INF) puts("impossible");
    else cout << res << endl;

    return 0;
}


            

活动打卡代码 AcWing 190. 字串变换

fangy
23小时前

                #include<iostream>
#include<queue>
#include<unordered_map> 
using namespace std;

#define st string
typedef unordered_map<string, int> UM;

int N;
st ST, ED, A[2][7]; 

int bfs(){
    if (ST == ED) return 0;
    queue<string> Q[2];
    UM d[2];
    Q[0].push(ST), d[0][ST] = 0;
    Q[1].push(ED), d[1][ED] = 0;

    while(!Q[0].empty() && !Q[1].empty()){
        int X = (Q[1].size() <= Q[0].size());
        for (int i = 0, leni = Q[X].size() ; i < leni ; i++){
            st S = Q[X].front();
            Q[X].pop();
            for (int j = 0, lenj = S.length() ; j < lenj ; j ++)
             for (int k = 0 ; k < N ; k++) 

               if (S.substr(j, A[X][k].length()) == A[X][k]){
                  st SS = S.substr(0, j) + A[X ^ 1][k] + S.substr(j + A[X][k].length());

                  if (d[X].count(SS)) continue;
                  if (d[X ^ 1].count(SS)) return d[X][S] + 1 + d[X ^ 1][SS];

                  d[X][SS] = d[X][S] + 1;
                  Q[X].push(SS);
               }
        }
    }
    return 233;
}

int main(){
    cin>>ST>>ED;
    while(cin>>A[0][N]>>A[1][N]) N++;
    int step = bfs();
    step > 10 ? printf("NO ANSWER!") : printf("%d", step);
}

            

活动打卡代码 AcWing 175. 电路维修

fangy
1天前

                #include <iostream>
#include <deque>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};

void bfs(int sx, int sy)
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);

    deque<PII> q;
    dist[sx][sy] = 0;
    q.push_back({sx, sy});

    while (q.size())
    {
        auto t = q.front();
        q.pop_front();

        int x = t.x, y = t.y;
        if (st[x][y]) continue;

        st[x][y] = true;

        string cs = "\\/\\/";
        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            if (st[a][b]) continue;

            int ca = x + ix[i], cb = y + iy[i];
            int d = dist[x][y] + (g[ca][cb] != cs[i]);

            if (d < dist[a][b])
            {
                dist[a][b] = d;
                if (g[ca][cb] == cs[i]) q.push_front({a, b});
                else q.push_back({a, b});
            }
        }
    }
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) scanf("%s", g[i]);

        if (n + m & 1) puts("NO SOLUTION");
        else
        {
            bfs(0, 0);
            cout << dist[n][m] << endl;
        }
    }

    return 0;
}

            

活动打卡代码 AcWing 3305. 作物杂交（每日一题）

fangy
1天前

                spfa算法，时间复杂度$O(m)$   spfa没死
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[N], targrt[M], idx;
int dist[N];
bool st[N];
queue<int> q;

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

void spfa()
{
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], k = targrt[i];
            if (dist[k] > max(dist[t], dist[j]) + max(w[t], w[j]))
            {
                dist[k] = max(dist[t], dist[j]) + max(w[t], w[j]);
                if (!st[k]) q.push(k), st[k] = true;
            }
        }
    }
}

int main()
{
    int k, T;
    cin >> n >> k >> m >> T;

    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

    memset(dist, 0x3f, sizeof dist);
    while (k--)
    {
        int x;
        scanf("%d", &x);
        dist[x] = 0;
        q.push(x);
        st[x] = true;
    }

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    spfa();

    cout << dist[T] << endl;

    return 0;
}


dijkstra算法，时间复杂度$O(n^2)$
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[N], targrt[M], idx;
int dist[N];
bool st[N];

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

void dijkstra()
{
    for (int i = 0; i < n - 1; ++i)
    {
        int t = 0;
        for (int i = 1; i <= n; ++i)
            if (!st[i] && dist[i] < dist[t])
                t = i;

        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], k = targrt[i];
            dist[k] = min(dist[k], max(dist[t], dist[j]) + max(w[t], w[j]));
        }
    }
}

int main()
{
    int k, T;
    cin >> n >> k >> m >> T;

    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

    memset(dist, 0x3f, sizeof dist);
    while (k--)
    {
        int x;
        scanf("%d", &x);
        dist[x] = 0;
    }

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dijkstra();

    cout << dist[T] << endl;

    return 0;
}

            

活动打卡代码 AcWing 4074. 铁路与公路（每日一题）

fangy
5天前

                #include <iostream>

using namespace std;

const int N = 410, INF = 1e9;

int n, m;
int d1[N][N], d2[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            if (i == j) d1[i][j] = d2[i][j] = 0;
            else d1[i][j] = INF, d2[i][j] = 1;
        }

    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d1[a][b] = d1[b][a] = 1;
        d2[a][b] = d2[b][a] = INF;
    }

    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]),
                d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);

    int res = max(d1[1][n], d2[1][n]);
    if (res > INF / 2) res = -1;

    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 854. Floyd求最短路（算法基础课）

fangy
5天前

                #include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 20010, INF = 1e9;

int n, m, q;
int dist[N][N];

void floyd()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        dist[a][b] = min(dist[a][b], c);
    }

    floyd();

    while (q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        if (dist[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", dist[a][b]);
    }

    return 0;
}

            

活动打卡代码 AcWing 852. spfa判断负环（算法基础课）

fangy
5天前

                #include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
bool used[N];

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

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i), st[i] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        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.push(j), st[j] = true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

spfa算法，时间复杂度$O(m)$ spfa没死

dijkstra算法，时间复杂度$O(n^2)$

0 评论

0 评论

0 评论

0 评论