首页 > 其他分享 >AcWing 1127. 香甜的黄油 (dij板子不能背太死, 需要知道含义灵活变通

AcWing 1127. 香甜的黄油 (dij板子不能背太死, 需要知道含义灵活变通

时间:2023-11-26 14:45:51浏览次数:32  
标签:PII ver dij int 1127 背太死 static new dis

package 算法提高课;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class acw1127 {
    static int n, p, c;
    static int[] id;
    static int[] h, e, ne, w;
    static boolean[] st;
    static int[] d;
    static int idx;

    static class PII implements Comparable {
        int dis, ver;

        public PII(int dis, int ver) {
            this.dis = dis;
            this.ver = ver;
        }

        @Override
        public int compareTo(Object o) {
            PII te = (PII) o;
            return this.dis - te.dis;
        }
    }

    private static void init() {
        h = new int[p + 10]; e = new int[2 * c + 10]; ne = new int[2 * c + 10]; w = new int[2 * c + 10];
        id = new int[p + 10]; st = new boolean[p + 10]; d = new int[p + 10];
        Arrays.fill(h, - 1);
    }

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

    private static int dij(int s) {
        Arrays.fill(d, 0x3f3f3f3f);
        Arrays.fill(st, false);
        d[s] = 0;
        PriorityQueue<PII> pq = new PriorityQueue<>();
        pq.add(new PII(0, s));

        while (!pq.isEmpty()) {
            PII te = pq.poll();
            int ver = te.ver, dis = te.dis;

            if (st[ver]) continue;
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (d[j] > dis + w[i]) {
                    d[j] = dis + w[i];
                    pq.add(new PII(d[j], j));
                }
            }
        }

        int ret = 0;
        for (int i = 1; i <= p; i ++ ) {
            if (d[i] == 0x3f3f3f3f && id[i] != 0) return 0x3f3f3f3f;
            ret += id[i] * d[i];
        }

        return ret;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); p = sc.nextInt(); c = sc.nextInt();
        init();

        for (int i = 1; i <= n; i ++ ) id[sc.nextInt()] ++ ;
        for (int i = 1; i <= c; i ++ ) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }

        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= p; i ++ ) ans = Math.min(ans, dij(i));
        System.out.println(ans);
    }
}

标签:PII,ver,dij,int,1127,背太死,static,new,dis
From: https://www.cnblogs.com/llihaotian666/p/17857185.html

相关文章

  • AcWing 1129. 热浪 (dij板子题
    package算法提高课;importjava.util.Arrays;importjava.util.PriorityQueue;importjava.util.Scanner;publicclassacw1129{staticclassPIIimplementsComparable{intdis,tar;//tar表示我这条边的入弧,dis表示我这条边的距离publicP......
  • AcWing 1128. 信使 (dij板子题 + 求花费最大的那个点的花费
    package算法提高课;importjava.util.Arrays;importjava.util.PriorityQueue;importjava.util.Scanner;publicclassacw1128{staticintn,m;staticint[]h,e,w,ne;staticint[]d;staticboolean[]st;staticintidx;staticclas......
  • Dijkstra 算法python版
    算法策略Dijkstra算法是求一个图中一个点到其他所有点的最短路径的算法,先了解图的数据结构「邻接矩阵」Dijkstra算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法,时间复杂度O(n2)B站视频:https://www.bilibili.com/vide......
  • dijkstra跑全源最短路
     跑n次voiddijk(){ for(inti=1;i<=n;i++) for(intj=1;j<=n;j++)d[i][j]=inf; priority_queue<pii,vector<pii>,greater<pii>>q; for(intS=1;S<=n;S++){ q.push(pii(0,S)); for(inti=1;i<=n;i++)......
  • Dijkstra算法
    Dijkstra算法1.算法基本介绍Dijkstra算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法,时间复杂度O(n2)。Dijkstra算法通常是求解单源最短路中最快的算法,但它无法处理存在负权边的情况(原因在正确性证明中)。Dijkstra本质......
  • Dijkstra, RIP, OSPF:OSPF算法
    RoutingInformationProtocol(RIP):Adistancevectorprotocolthatuseshopcountasitsmetrictodeterminethebestpathforroutingpackets.OpenShortestPathFirst(OSPF):Alinkstateprotocolthatcalculatesroutesbasedontheshortestpathalgor......
  • Dijkstra, RIP, OSPF:RIP算法
    这部分参考王道bilibili视频:https://www.bilibili.com/video/BV19E411D78Q?p=56&vd_source=63764dd9776224d187bddddb05bf9f3f 例题-1:R6、R4相邻,如左图所示。现在R4的路由表更新为右上表,现在让你写出R6更新后的路由表。  例题-2:这道题中向量6个元素分别代表某个路......
  • dijkstra模板
    暴力—时间复杂度O(n^2)intne[N],h[N],idx,e[N],wt[N];//wt[]表示边权voidadd(intu,intv,intw)//链式前向星存图{idx++;e[idx]=v;wt[idx]=w;//边权ne[idx]=h[u];h[u]=idx;}intvis[N];//vis[i]表示i点是否在s集合中intd[N];//d[i]表示......
  • 【迪杰斯特拉】Dijkstra
    前言此乃一个小Oler的一篇图论算法随笔,从今日后,还会进行详细的修订。一、简单介绍(Dijkstra)迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰......
  • Dijkstra
    Dijkstra初始版本:1.思路分析:用vis数组记录每个点是否被访问过。从原点开始拓展n-1次,计算到每个点的最小距离。每次循环寻找一个距离原点最近的点,然后做松弛操作,更新那些距离更远点。时间复杂度O(n^2)。算法板子:点击查看代码#include<bits/stdc++.h>usingnamespacestd......