배터리를 갈며 나는 드론

import heapqimport sys data = sys.stdin.read().split()n, m = int(data[0]), int(data[1])swap = [0] + [int(x) for x in data[2 : 2 + n]]  # swap[v] = v번에서 배터리를 가는 데 걸리는 초 routes = [[] for _ in range(n + 1)]  # routes[a] = a에서 떠나는 (도착, 초) 항로들for i in range(m):    k = 2 + n + 3 * i    a, b, w = int(data[k]), int(data[k + 1]), int(data[k + 2])    routes[a].append((b, w)) INF = -1best = [INF] * (n + 1)  # 지금까지 찾은 가장 짧은 시간(-1은 아직 못 감)done = [False] * (n + 1)  # 가장 짧은 시간이 확정된 중계소best[1] = 0heap = [(0, 1)]  # (시간, 중계소): 늘 가장 작은 시간을 먼저 꺼낸다while heap:    t, v = heapq.heappop(heap)    if done[v]:        continue  # 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)    done[v] = True    leave = t if v == 1 else t + swap[v]  # 처음 1번을 떠날 때만 배터리를 갈지 않는다    for nxt, w in routes[v]:        if best[nxt] == INF or leave + w < best[nxt]:            best[nxt] = leave + w            heapq.heappush(heap, (leave + w, nxt)) print(" ".join(map(str, best[1:])))

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: 칸마다 [시간, 중계소]. heap[0]이 가장 작은 시간이고, i의 자식은 2i+1, 2i+2class MinHeap {  constructor() {    this.items = [];  }  get size() {    return this.items.length;  }  push(x) {    const a = this.items;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const parent = (i - 1) >> 1;      if (a[parent][0] <= a[i][0]) break;      [a[parent], a[i]] = [a[i], a[parent]];      i = parent;    }  }  pop() {    const a = this.items;    const top = a[0];    const last = a.pop();    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1, r = l + 1;        let small = i;        if (l < a.length && a[l][0] < a[small][0]) small = l;        if (r < a.length && a[r][0] < a[small][0]) small = r;        if (small === i) break;        [a[small], a[i]] = [a[i], a[small]];        i = small;      }    }    return top;  }} const swap = [0, ...data.slice(2, 2 + n)]; // swap[v] = v번에서 배터리를 가는 데 걸리는 초const routes = Array.from({ length: n + 1 }, () => []); // routes[a] = a에서 떠나는 [도착, 초] 항로들for (let i = 0; i < m; i++) {  const k = 2 + n + 3 * i;  routes[data[k]].push([data[k + 1], data[k + 2]]);} const best = new Array(n + 1).fill(-1); // 지금까지 찾은 가장 짧은 시간(-1은 아직 못 감)const done = new Array(n + 1).fill(false); // 가장 짧은 시간이 확정된 중계소best[1] = 0;const heap = new MinHeap();heap.push([0, 1]);while (heap.size > 0) {  const [t, v] = heap.pop();  if (done[v]) continue; // 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)  done[v] = true;  const leave = v === 1 ? t : t + swap[v]; // 처음 1번을 떠날 때만 배터리를 갈지 않는다  for (const [next, w] of routes[v]) {    if (best[next] === -1 || leave + w < best[next]) {      best[next] = leave + w;      heap.push([leave + w, next]);    }  }}console.log(best.slice(1).join(" "));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; type Entry = [time: number, station: number]; // 최소 힙: heap[0]이 가장 작은 시간이고, i의 자식은 2i+1, 2i+2class MinHeap {  private items: Entry[] = [];   get size(): number {    return this.items.length;  }   push(x: Entry): void {    const a = this.items;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const parent = (i - 1) >> 1;      if (a[parent][0] <= a[i][0]) break;      [a[parent], a[i]] = [a[i], a[parent]];      i = parent;    }  }   pop(): Entry {    const a = this.items;    const top = a[0];    const last = a.pop()!; // size > 0일 때만 부른다    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1, r = l + 1;        let small = i;        if (l < a.length && a[l][0] < a[small][0]) small = l;        if (r < a.length && a[r][0] < a[small][0]) small = r;        if (small === i) break;        [a[small], a[i]] = [a[i], a[small]];        i = small;      }    }    return top;  }} const swap: number[] = [0, ...data.slice(2, 2 + n)]; // swap[v] = v번에서 배터리를 가는 데 걸리는 초// routes[a] = a에서 떠나는 [도착, 초] 항로들const routes: [number, number][][] = Array.from({ length: n + 1 }, (): [number, number][] => []);for (let i = 0; i < m; i++) {  const k = 2 + n + 3 * i;  routes[data[k]].push([data[k + 1], data[k + 2]]);} const best: number[] = new Array<number>(n + 1).fill(-1); // 지금까지 찾은 가장 짧은 시간(-1은 아직 못 감)const done: boolean[] = new Array<boolean>(n + 1).fill(false); // 가장 짧은 시간이 확정된 중계소best[1] = 0;const heap = new MinHeap();heap.push([0, 1]);while (heap.size > 0) {  const [t, v] = heap.pop();  if (done[v]) continue; // 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)  done[v] = true;  const leave = v === 1 ? t : t + swap[v]; // 처음 1번을 떠날 때만 배터리를 갈지 않는다  for (const [next, w] of routes[v]) {    if (best[next] === -1 || leave + w < best[next]) {      best[next] = leave + w;      heap.push([leave + w, next]);    }  }}console.log(best.slice(1).join(" "));

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        int n = Integer.parseInt(st.nextToken());        int m = Integer.parseInt(st.nextToken());        int[] swap = new int[n + 1]; // swap[v] = v번에서 배터리를 가는 데 걸리는 초        st = new StringTokenizer(in.readLine());        for (int v = 1; v <= n; v++) swap[v] = Integer.parseInt(st.nextToken());         List<List<int[]>> routes = new ArrayList<>(); // routes.get(a) = a에서 떠나는 {도착, 초} 항로들        for (int v = 0; v <= n; v++) routes.add(new ArrayList<>());        for (int i = 0; i < m; i++) {            st = new StringTokenizer(in.readLine());            int a = Integer.parseInt(st.nextToken());            int b = Integer.parseInt(st.nextToken());            int w = Integer.parseInt(st.nextToken());            routes.get(a).add(new int[] {b, w});        }         long[] best = new long[n + 1]; // 시간의 합은 int(약 21억)를 넘을 수 있다        Arrays.fill(best, -1);        boolean[] done = new boolean[n + 1];        best[1] = 0;        // {시간, 중계소}를 시간이 작은 것부터 꺼내는 최소 힙        PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));        heap.add(new long[] {0, 1});        while (!heap.isEmpty()) {            long[] top = heap.poll();            long t = top[0];            int v = (int) top[1];            if (done[v]) continue; // 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)            done[v] = true;            long leave = v == 1 ? t : t + swap[v]; // 처음 1번을 떠날 때만 배터리를 갈지 않는다            for (int[] r : routes.get(v)) {                int next = r[0];                if (best[next] == -1 || leave + r[1] < best[next]) {                    best[next] = leave + r[1];                    heap.add(new long[] {best[next], next});                }            }        }         StringBuilder out = new StringBuilder();        for (int v = 1; v <= n; v++) {            if (v > 1) out.append(' ');            out.append(best[v]);        }        System.out.println(out);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]);        int m = int.Parse(first[1]);        var swap = new int[n + 1]; // swap[v] = v번에서 배터리를 가는 데 걸리는 초        string[] swaps = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        for (int v = 1; v <= n; v++) swap[v] = int.Parse(swaps[v - 1]);         var routes = new List<(int to, int w)>[n + 1]; // routes[a] = a에서 떠나는 항로들        for (int v = 0; v <= n; v++) routes[v] = new List<(int to, int w)>();        for (int i = 0; i < m; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            routes[int.Parse(p[0])].Add((int.Parse(p[1]), int.Parse(p[2])));        }         var best = new long[n + 1]; // 시간의 합은 int(약 21억)를 넘을 수 있다        Array.Fill(best, -1L);        var done = new bool[n + 1];        best[1] = 0;        // PriorityQueue<값, 우선순위>: 우선순위(시간)가 작은 것부터 나온다        var heap = new PriorityQueue<(long t, int v), long>();        heap.Enqueue((0, 1), 0);        while (heap.Count > 0)        {            var (t, v) = heap.Dequeue();            if (done[v]) continue; // 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)            done[v] = true;            long leave = v == 1 ? t : t + swap[v]; // 처음 1번을 떠날 때만 배터리를 갈지 않는다            foreach (var (next, w) in routes[v])            {                if (best[next] == -1 || leave + w < best[next])                {                    best[next] = leave + w;                    heap.Enqueue((best[next], next), best[next]);                }            }        }         var sb = new StringBuilder();        for (int v = 1; v <= n; v++)        {            if (v > 1) sb.Append(' ');            sb.Append(best[v]);        }        Console.WriteLine(sb.ToString());    }}

#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, m;    std::cin >> n >> m;    std::vector<int> swap_time(n + 1); // swap_time[v] = v번에서 배터리를 가는 데 걸리는 초    for (int v = 1; v <= n; v++) std::cin >> swap_time[v];     std::vector<std::vector<std::pair<int, int>>> routes(n + 1); // routes[a] = a에서 떠나는 (도착, 초) 항로들    for (int i = 0; i < m; i++) {        int a, b, w;        std::cin >> a >> b >> w;        routes[a].push_back({b, w});    }     std::vector<long long> best(n + 1, -1); // 시간의 합은 int(약 21억)를 넘을 수 있다    std::vector<bool> done(n + 1, false);    // std::priority_queue는 기본이 최대 힙이라 std::greater를 줘서 가장 작은 시간이 위로 오게 한다    using Entry = std::pair<long long, int>; // (시간, 중계소)    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;    best[1] = 0;    heap.push({0, 1});    while (!heap.empty()) {        auto [t, v] = heap.top();        heap.pop();        if (done[v]) continue; // 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록)        done[v] = true;        long long leave = v == 1 ? t : t + swap_time[v]; // 처음 1번을 떠날 때만 배터리를 갈지 않는다        for (auto [next, w] : routes[v]) {            if (best[next] == -1 || leave + w < best[next]) {                best[next] = leave + w;                heap.push({best[next], next});            }        }    }     for (int v = 1; v <= n; v++) std::cout << (v > 1 ? " " : "") << best[v];    std::cout << "\n";}

#include <stdio.h> #define MAXN 10001#define MAXM 10000 /* 인접 목록을 배열로: head[a]는 a에서 떠나는 첫 항로 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM], cost[MAXM];static int swap_time[MAXN]; /* swap_time[v] = v번에서 배터리를 가는 데 걸리는 초 */static long long best[MAXN]; /* 시간의 합은 int(약 21억)를 넘을 수 있다 */static int done[MAXN]; /* 최소 힙: 칸마다 (시간, 중계소). heap_t[0]이 가장 작다 */static long long heap_t[MAXM + 1];static int heap_v[MAXM + 1], heap_size = 0; static void heap_swap(int i, int j) {    long long t = heap_t[i];    heap_t[i] = heap_t[j];    heap_t[j] = t;    int v = heap_v[i];    heap_v[i] = heap_v[j];    heap_v[j] = v;} static void heap_push(long long t, int v) {    int i = heap_size++;    heap_t[i] = t;    heap_v[i] = v;    while (i > 0 && heap_t[(i - 1) / 2] > heap_t[i]) {        heap_swap((i - 1) / 2, i);        i = (i - 1) / 2;    }} static void heap_pop(long long* t, int* v) {    *t = heap_t[0];    *v = heap_v[0];    heap_size--;    heap_t[0] = heap_t[heap_size];    heap_v[0] = heap_v[heap_size];    int i = 0;    for (;;) {        int l = 2 * i + 1, r = l + 1, small = i;        if (l < heap_size && heap_t[l] < heap_t[small]) small = l;        if (r < heap_size && heap_t[r] < heap_t[small]) small = r;        if (small == i) break;        heap_swap(small, i);        i = small;    }} int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int v = 1; v <= n; v++) {        head[v] = -1;        best[v] = -1; /* -1은 아직 못 감 */        scanf("%d", &swap_time[v]);    }    for (int e = 0; e < m; e++) {        int a;        scanf("%d %d %d", &a, &to[e], &cost[e]);        next[e] = head[a];        head[a] = e;    }     best[1] = 0;    heap_push(0, 1);    while (heap_size > 0) {        long long t;        int v;        heap_pop(&t, &v);        if (done[v]) continue; /* 더 짧은 시간으로 이미 꺼낸 중계소(남아 있던 옛 기록) */        done[v] = 1;        long long leave = v == 1 ? t : t + swap_time[v]; /* 처음 1번을 떠날 때만 배터리를 갈지 않는다 */        for (int e = head[v]; e != -1; e = next[e]) {            int b = to[e];            if (best[b] == -1 || leave + cost[e] < best[b]) {                best[b] = leave + cost[e];                heap_push(best[b], b);            }        }    }     for (int v = 1; v <= n; v++) printf(v > 1 ? " %lld" : "%lld", best[v]);    putchar('\n');    return 0;}

// 최소 힙(목록 heap): 칸마다 [시간, 중계소]. heap[0]이 가장 작은 시간이고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){    heap.넣기(x);    i = heap.개수 - 1;    동안 (i > 0)    {        부모 = 수학.몫(i - 1, 2);        만약 (heap[부모][0] <= heap[i][0])        {            그만;        }        t = heap[부모];        heap[부모] = heap[i];        heap[i] = t;        i = 부모;    }} 힙꺼내기(heap){    top = heap[0];    heap[0] = heap[heap.개수 - 1];    heap.자리빼기(heap.개수 - 1);    i = 0;    동안 (참)    {        l = 2 * i + 1;        r = l + 1;        small = i;        만약 (l < heap.개수 && heap[l][0] < heap[small][0])        {            small = l;        }        만약 (r < heap.개수 && heap[r][0] < heap[small][0])        {            small = r;        }        만약 (small == i)        {            그만;        }        t = heap[small];        heap[small] = heap[i];        heap[i] = t;        i = small;    }    돌려주기 top;} 첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];swap = 콘솔.수들읽기(); // swap[v] = v번(0번부터)에서 배터리를 가는 데 걸리는 초 // 목록은 10,000칸까지라 중계소 번호에서 1을 빼 0번부터 둔다routes = []; // routes[a] = a에서 떠나는 [도착, 초] 항로들반복 (v = 0; v < n; v++){    routes.넣기([]);}반복 (i = 0; i < m; i++){    항로 = 콘솔.수들읽기();    routes[항로[0] - 1].넣기([항로[1] - 1, 항로[2]]);} best = 새목록(n, -1); // 지금까지 찾은 가장 짧은 시간(-1은 아직 못 감)done = 새목록(n, 거짓); // 가장 짧은 시간이 확정된 중계소best[0] = 0;heap = [[0, 0]];동안 (heap.개수 > 0){    꺼낸것 = 힙꺼내기(heap);    t = 꺼낸것[0];    v = 꺼낸것[1];    만약 (!done[v])    {        done[v] = 참;        leave = t + swap[v]; // 처음 1번(0번 칸)을 떠날 때만 배터리를 갈지 않는다        만약 (v == 0)        {            leave = t;        }        각각 (항로 에서 routes[v])        {            next = 항로[0];            만약 (best[next] == -1 || leave + 항로[1] < best[next])            {                best[next] = leave + 항로[1];                힙넣기(heap, [best[next], next]);            }        }    }}콘솔.쓰기(best);