SHARE
TWEET

Untitled

a guest Nov 17th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class FVol3 {
  4.     public static void main(String[] args) {
  5.         Scanner stdin = new Scanner(System.in);
  6.  
  7.         int n = stdin.nextInt();
  8.         int t = stdin.nextInt();
  9.  
  10.         Grafo graph = new Grafo(n);
  11.         int[] prec = new int[n + 1];
  12.  
  13.         for (int i = 0; i < t; i++) {
  14.             int from = stdin.nextInt();
  15.             int to = stdin.nextInt();
  16.             int val = stdin.nextInt();
  17.             graph.insert_new_arc(from, to, val);
  18.             prec[to]++;
  19.         }
  20.  
  21.         int[] es = new int[n + 1];
  22.  
  23.         int[] starts = new int[t];
  24.         int[] ends = new int[t];
  25.  
  26.         Queue<Integer> queue = new LinkedList<>();
  27.  
  28.         queue.add(1);
  29.  
  30.         int tnum = 0;
  31.  
  32.         while (!queue.isEmpty()) {
  33.             int node = queue.remove();
  34.             for (Arco task : graph.adjs_no(node)) {
  35.                 int end = task.extremo_final();
  36.                 int duration = task.valor_arco();
  37.                 if (es[end] < es[node] + duration)
  38.                     es[end] = es[node] + duration;
  39.                 starts[tnum] = es[node];
  40.                 ends[tnum] = es[node] + duration;
  41.                 tnum++;
  42.                 prec[end]--;
  43.                 if (prec[end] == 0)
  44.                     queue.add(end);
  45.             }
  46.         }
  47.  
  48.         Arrays.sort(starts);
  49.         Arrays.sort(ends);
  50.  
  51.         int currentTasks = 1;
  52.         int maxTasks = 1;
  53.         int time = starts[0];
  54.         int i = 1, j = 0;
  55.  
  56.         while (i < t && j < t) {
  57.             if (starts[i] < ends[j]) {
  58.                 currentTasks++;
  59.                 if (currentTasks > maxTasks) {
  60.                     maxTasks = currentTasks;
  61.                     time = starts[i];
  62.                 }
  63.                 i++;
  64.             } else {
  65.                 currentTasks--;
  66.                 j++;
  67.             }
  68.         }
  69.  
  70.         System.out.println(es[n] + " " + maxTasks + " " + time);
  71.     }
  72. }
  73.  
  74. class Arco {
  75.     int no_final;
  76.     int valor;
  77.  
  78.     Arco(int fim, int v) {
  79.         no_final = fim;
  80.         valor = v;
  81.     }
  82.  
  83.     int extremo_final() {
  84.         return no_final;
  85.     }
  86.  
  87.     int valor_arco() {
  88.         return valor;
  89.     }
  90.  
  91.     void novo_valor(int v) {
  92.         valor = v;
  93.     }
  94. }
  95.  
  96. class No {
  97.     // int label;
  98.     LinkedList<Arco> adjs;
  99.  
  100.     No() {
  101.         adjs = new LinkedList<Arco>();
  102.     }
  103. }
  104.  
  105. class Grafo {
  106.     No verts[];
  107.     int nvs, narcos;
  108.  
  109.     public Grafo(int n) {
  110.         nvs = n;
  111.         narcos = 0;
  112.         verts = new No[n + 1];
  113.         for (int i = 0; i <= n; i++)
  114.             verts[i] = new No();
  115.         // para vertices numerados de 1 a n (posicao 0 nao vai ser usada)
  116.     }
  117.  
  118.     public int num_vertices() {
  119.         return nvs;
  120.     }
  121.  
  122.     public int num_arcos() {
  123.         return narcos;
  124.     }
  125.  
  126.     public LinkedList<Arco> adjs_no(int i) {
  127.         return verts[i].adjs;
  128.     }
  129.  
  130.     public void insert_new_arc(int i, int j, int valor_ij) {
  131.         verts[i].adjs.addFirst(new Arco(j, valor_ij));
  132.         narcos++;
  133.     }
  134.  
  135.     public Arco find_arc(int i, int j) {
  136.         for (Arco adj : adjs_no(i))
  137.             if (adj.extremo_final() == j)
  138.                 return adj;
  139.         return null;
  140.     }
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top