A delivery drone uses n relay stations numbered 1 to n.
Between the stations there are m routes that can be flown in one direction only.
A route "a b w" means the drone can fly from station a to station b in w seconds.
A route cannot be used in the opposite direction, and there may be several routes with different times between the same two stations.
Before leaving any station the drone must swap its battery there, and swapping the battery at station i takes cᵢ seconds.
The drone starts from station 1 at second 0 with a full battery, so only the first time it leaves station 1 does it not swap (if it later comes back to station 1 and leaves again, it swaps).
Nothing takes time except swapping batteries and flying.
The arrival time at a station is the moment the drone lands there; the battery swap at that station is not included.
Print the earliest arrival time at each station from 1 to n, in order, on one line separated by spaces.
The value for station 1 is 0.
Print -1 for a station that no sequence of routes reaches.
Input
The first line has n and m, the second line c₁ … cₙ, and each of the next m lines a, b, w, all separated by spaces. 1 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 0 ≤ cᵢ ≤ 1,000,000, 1 ≤ a, b ≤ n, a ≠ b, 1 ≤ w ≤ 1,000,000
Output
n numbers (the earliest arrival time at each station, or -1) on one line, separated by spaces
Example 1 · stdin
5 6
5 1 0 2 3
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 1 3
stdout
0 3 1 9 -1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Attach the battery time to the station being left: if the drone lands at v at time t, it leaves v at t + c[v] (just t if v is station 1), and one route brings it to leave time + w. All times are 0 or more, so the earliest times come from Dijkstra's algorithm: put (time, station) in a min-heap and always take the smallest time; the first time a station comes out, its time is final (no later path can arrive earlier). If a station goes in again with an earlier time, the old entry stays in the heap, so when one comes out for a station already final (done), skip it. Station 1 is final at 0 right away, so leaving station 1 is computed only once, and that is the "first departure", with no swap. Trap one: fixing the first time you reach a station, like breadth-first search, is wrong — in the example station 2 is 4 seconds directly but 3 seconds through station 3 (a 0-second swap). Trap two: swapping at station 1 too (adding c[1]), or adding the swap time of the station you arrive at, is wrong — batteries are swapped only when leaving, and not at the first departure from station 1. Trap three: a time can reach 9,999 × (1,000,000 + 1,000,000) ≈ 20 billion, past a 32-bit int (about 2.1 billion). C and C++ need long long, Java and C# long (a Java or C# int wraps around to a negative number); Python integers have no size limit, and JavaScript, TypeScript and Craykon numbers are doubles, exact up to 2^53 (about 9×10^15), so they work as they are. Trap four: C++ std::priority_queue is a max-heap by default, so the latest time comes out first — it needs std::greater<std::pair<long long, int>>. Heaps differ by language: Python heapq compares the tuple (time, station) from the first item, so it just works; Java PriorityQueue<long[]> takes the compare function (x, y) -> Long.compare(x[0], y[0]); C# PriorityQueue<(long t, int v), long> takes the value and the priority (the time) separately. JavaScript, TypeScript, C and Craykon have no heap, so build one on a list (array): the parent of i is (i - 1) / 2 (integer division — Craykon Mathf.Quot(i - 1, 2)), the children 2i + 1 and 2i + 2. Craykon lists hold up to 10,000 items, so it subtracts 1 from each number to start at 0 (NewList(n, -1)), and since pushing starts only after station 1 is taken out, the heap holds at most m entries. Writing the list as Console.WriteLine(best) joins it with spaces.
Pythonmain.py · 30 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 최소 힙(목록 heap): 칸마다 [시간, 중계소]. heap[0]이 가장 작은 시간이고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.Add(x); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (heap[부모][0] <= heap[i][0]) { break; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙꺼내기(heap){ top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; small = i; if (l < heap.Count && heap[l][0] < heap[small][0]) { small = l; } if (r < heap.Count && heap[r][0] < heap[small][0]) { small = r; } if (small == i) { break; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; } return top;}첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];swap = Console.ReadNumbers(); // swap[v] = v번(0번부터)에서 배터리를 가는 데 걸리는 초// 목록은 10,000칸까지라 중계소 번호에서 1을 빼 0번부터 둔다routes = []; // routes[a] = a에서 떠나는 [도착, 초] 항로들for (v = 0; v < n; v++){ routes.Add([]);}for (i = 0; i < m; i++){ 항로 = Console.ReadNumbers(); routes[항로[0] - 1].Add([항로[1] - 1, 항로[2]]);}best = NewList(n, -1); // 지금까지 찾은 가장 짧은 시간(-1은 아직 못 감)done = NewList(n, false); // 가장 짧은 시간이 확정된 중계소best[0] = 0;heap = [[0, 0]];while (heap.Count > 0){ 꺼낸것 = 힙꺼내기(heap); t = 꺼낸것[0]; v = 꺼낸것[1]; if (!done[v]) { done[v] = true; leave = t + swap[v]; // 처음 1번(0번 칸)을 떠날 때만 배터리를 갈지 않는다 if (v == 0) { leave = t; } foreach (항로 in routes[v]) { next = 항로[0]; if (best[next] == -1 || leave + 항로[1] < best[next]) { best[next] = leave + 항로[1]; 힙넣기(heap, [best[next], next]); } } }}Console.WriteLine(best);