leetcode第 284 场周赛（AC 3道，排名818 / 8483）

题目

1. 找出数组中的所有 K 近邻下标
2. 统计可以提取的工件
3. K 次操作后最大化顶端元素
4. 得到要求路径的最小带权子图

题解

只做出来前3道，最后一题只知道用dijkstra算法，但没有太多时间进一步考虑，还是不够熟练。

6031 找出数组中的所有 K 近邻下标

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        key_index = []
        for i in range(len(nums)):
            if nums[i]==key:
                key_index.append(i)
        
        ret_set = set()
        for index in key_index:
            for i in range(index-k, index+k+1):
                if 0<=i<len(nums):
                    ret_set.add(i)
        return list(ret_set)

5203 统计可以提取的工件

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        dig_set = set(((l[0],l[1]) for l in dig))
        ret = 0
        for art in artifacts:
            r1i, c1i, r2i, c2i = art
            flag = True
            for r in range(r1i, r2i+1):
                for c in range(c1i, c2i+1):
                    if (r, c) not in dig_set:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                ret += 1
        return ret

5227 K 次操作后最大化顶端元素

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        n = len(nums)
        min_val, max_val = min(nums), max(nums)
        
        # 元素全部相等，可能出现空栈的情况
        if min_val==max_val:
            if k>=n and (k-n)&1==0:
                return -1
            else:
                return max_val
        
        if k>n:
            return max_val
        
        if k==0:
            return nums[0]
        
        if k==1:
            return nums[1]
        
        nums.append(-1)
        pre_max = max(nums[:k-1])
        return max(pre_max, nums[k])

6032 得到要求路径的最小带权子图

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        def dijkstra(src, w):
            dist = [float('inf') for _ in range(n)]
            dist[src] = 0
            
            visited = [False for _ in range(n)]
            
            for _ in range(n):
                min_dist = float('inf')
                min_i = -1
                for i in range(n):
                    if not visited[i] and dist[i]<min_dist:
                        min_dist = dist[i]
                        min_i = i
                
                visited[min_i] = True
                for i in range(n):
                    dist[i] = min(dist[i], min_dist + w[min_i][i])
            return dist
                
            
        w = [[float('inf') for _ in range(n)] for _ in range(n)]
        for i in range(n):
            w[i][i] = 0
        for e in edges:
            w[e[0]][e[1]] = min(w[e[0]][e[1]], e[2])
        
        dist1 = dijkstra(src1, w)
        dist2 = dijkstra(src2, w)
        
        w_1_dest = dist1[dest]
        w_2_dest = dist2[dest]
        w_1_2 = dist1[src2]
        w_2_1 = dist2[src1]
        
        if w_1_dest==float('inf') or w_2_dest==float('inf'):
            return -1
        
        ret = w_1_dest + w_2_dest
        
        if w_1_2 < float('inf'):
            ret = min(w_1_2 + w_2_dest, ret)
        
        if w_2_1 < float('inf'):
            ret = min(w_2_1 + w_1_dest, ret)
        
        return ret

就这已经超时了。看到大神的答案，应该用3次dijkstra，最后一次是反向的。

难得见到一个排行榜前列用python的 @pku_erutan：

class CGraph_weight() :
    def __init__(self, edges) :
        self.link_dict = collections.defaultdict(dict)

        for s, e, w in edges :
            if e in self.link_dict[s] :
                self.link_dict[s][e] = min(self.link_dict[s][e], w)
            else :
                self.link_dict[s][e] = w

    def bfs(self, source) :
        """
        单源最短路径
        """
        visited = {}
        to_visit = [[0, source]]

        while len(to_visit) > 0 :
            cost, pnow = heapq.heappop(to_visit)
            if pnow in visited:
                continue
            visited[pnow] = cost

            for pnext in self.link_dict[pnow] :
                if pnext in visited :
                    continue
                heapq.heappush(to_visit, [cost+self.link_dict[pnow][pnext], pnext])
        return visited
class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        
        cgraph = CGraph_weight(edges)
        rcgraph = CGraph_weight([[t, s, w] for s, t, w in edges])
        dis1 = cgraph.bfs(src1)
        dis2 = cgraph.bfs(src2)
        dist = rcgraph.bfs(dest)
        print(dis1)
        print(dis2)
        print(dist)
        to_ret = 1e99
        for mid in range(n) :
            if not mid in dis1 or not mid in dis2 or not mid in dist :
                continue
            to_ret = min(to_ret, dis1[mid]+dis2[mid]+dist[mid])
        if to_ret > 1e88 :
            return -1
        return to_ret

榜一@RobeZH的C++解法很漂亮，学习了：

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define subnb true
#define Lnb true
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll INF = (ll)1e18;

class Solution {
public:
    struct edge {
        int to, cost;
    };
    vector<vector<edge>> G, rG;

    vector<ll> dijkstra(int s, int n, vector<vector<edge>> &S) {
        vector<ll> dist(n, INF);
        dist[s] = 0;
        priority_queue<pll, vector<pll>, greater<pll> > pque;
        pque.push({0, s});
        while(!pque.empty()) {
            auto p = pque.top(); pque.pop();
            ll v = p.second, d = p.first;
            if(dist[v] < d) continue;
            for (auto &e : S[v]) {
                if(dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    pque.push({dist[e.to], e.to});
                }
            }
        }
        return dist;
    }

    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        G = vector<vector<edge>>(n);
        rG = vector<vector<edge>>(n);
        for (auto &v : edges) {
            G[v[0]].push_back({v[1], v[2]});
            rG[v[1]].push_back({v[0], v[2]});
        }
        auto dsrc1 = dijkstra(src1, n, G);
        auto dsrc2 = dijkstra(src2, n, G);
        auto ddest = dijkstra(dest, n, rG);
        ll res = INF;
        rep(i, 0, n) {
            res = min(res, dsrc1[i] + dsrc2[i] + ddest[i]);
        }
        if(res >= INF) return -1;
        else return res;
    }
};