Ping

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package kilo;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 *
 * @author asjuvone
 */
public class Ping {
    
    public static int n;
    public static int q;
    public static int p;
    public static ArrayList<Kaari>[] verkko;

    public static void main(String[] args) {
        IO io = new IO();

        n = io.nextInt();
        q = io.nextInt();
        p = io.nextInt();

        verkko = new ArrayList[n + 1];
        verkko[0] = new ArrayList();

        for (int i = 1; i <= n; i++) {
            verkko[i] = new ArrayList();
        }

        for (int i = 1; i <= q; i++) {
            int a = io.nextInt();
            int b = io.nextInt();
            int paino = io.nextInt();

            verkko[a].add(new Kaari(i, paino, b));
            verkko[b].add(new Kaari(i, paino, a));

        }

//        for (int i=1; i<=n; i++) {
//            ArrayList<Kaari> kaaret = verkko[i];
//            for (int j = 0; j < kaaret.size(); j++) {
//                System.out.println("Kaaresta " + i + " pääsee " + kaaret.get(j));
//            }
//        }
        
       
        
        int alku = 1, loppu = q;
        
        while (alku < loppu) {
            int keski = (alku+loppu) / 2;
            long tulos = dijkstra(keski);
            if (tulos <= p) {
                loppu = keski;
            } else {
                alku = keski + 1;
            }
            //System.out.println("alku=" + alku);
        }
        //System.out.println("alku=" + alku + " pingi=" + dijkstra(alku));
        
              //  System.out.println("dijkstra at 4=" + dijkstra(4));
        if (dijkstra(alku) <= p) io.println(alku);
        else if (dijkstra(alku-1) <= p) io.println(alku-1);
        else io.println("QAQ");
        io.close();
        

    }
    
    public static long dijkstra(int aika) {
        PriorityQueue<Kaari> kaaret = new PriorityQueue<>();
        kaaret.add(new Kaari(1, 0, 1));
        
        boolean[] kayty = new boolean[n+1];
        while (!kaaret.isEmpty()) {
            Kaari nyk = kaaret.poll();
            if (kayty[nyk.kohde]) continue;
            kayty[nyk.kohde] = true;
            //System.out.println("kaytiin kohde " + nyk.kohde + " hetkella " + nyk.hetki);
            if (nyk.kohde == n) return nyk.paino;
            for (Kaari seur : verkko[nyk.kohde]) {
                 if (seur.hetki > aika) continue;
                 Kaari uusi = new Kaari(seur.hetki, nyk.paino + seur.paino, seur.kohde);
                 kaaret.add(uusi);
            }
        }
        return Long.MAX_VALUE;
    }

}

class Kaari implements Comparable<Kaari> {

    int kohde;
    int hetki;
    long paino;

    public Kaari(int hetki, long paino, int kohde) {
        this.kohde = kohde;
        this.hetki = hetki;
        this.paino = paino;
    }

    public String toString() {
        return "kohde: " + kohde;
    }

    @Override
    public int compareTo(Kaari o) {
        
        if (o.paino < this.paino) return 1;
        if (o.paino > this.paino) return -1;
        return 0;
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED