import heapqimport sysdata = 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:])))
JavaScriptmain.js · 68 行
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(" "));
TypeScriptmain.ts · 74 行
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(" "));
JavaMain.java · 60 行
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); }}
C#Main.cs · 55 行
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()); }}
C++main.cpp · 45 行
#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";}
Cmain.c · 88 行
#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;}
Craykonmain.cray · 96 行
// 최소 힙(목록 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);