LeetCode Weekly Contest 206 3問目 - Min Cost to Connect All Points [1584]

Source

LeetCode Weekly Contest 206
問題文

問題概要

省略

解法

省略

cLay（version 20200913-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

int N, X[1000], Y[1000];
int m, a[1d6], b[1d6], c[1d6];

class Solution {
public:
  int minCostConnectPoints(vector<vector<int>>& points) {
    dummy_main();
    int res = 0;
    unionFind uf;

    N = points.size();
    rep(i,N) (X[i], Y[i]) = (points[i][0], points[i][1]);
    m = 0;
    rep(i,N) rep(j,i+1,N) arrInsert(m, m, a, i, b, j, c, abs(X[i]-X[j])+abs(Y[i]-Y[j]));
    sortA(m, c, a, b);

    uf.walloc(N, 1);
    rep(i,m) if(uf(a[i],b[i])) res += c[i];
    return res;
  }
};

Current time: 2024年04月25日18時39分29秒
Last modified: 2020年09月13日13時49分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)