Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class t178 {
- static class edge {
- int a, b, cost;
- public edge(int a, int b, int cost) {
- this.a = a;
- this.b = b;
- this.cost = cost;
- }
- }
- static edge[] e;
- static int[] d;
- static final int t = 30000;
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int m = in.nextInt();
- e = new edge[m + 1];
- d = new int[n + 1];
- for (int i = 1; i < m + 1; i++) {
- e[i] = new edge(in.nextInt(), in.nextInt(), in.nextInt());
- }
- for (int i = 2; i < n + 1; i++) {
- d[i] = t;
- }
- for (int i = 0; i < n - 1; i++) {
- for (int j = 1; j < m + 1; j++) {
- if (d[e[j].a] < t) {
- d[e[j].b] = Math.min(d[e[j].b], d[e[j].a] + e[j].cost);
- }
- }
- }
- for (int i = 1; i < n; i++) {
- System.out.print(d[i] + " ");
- }
- System.out.println(d[n]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement