Lennot

import java.util.*;

public class Tehtava4 {
	
	private static HashMap<Integer, ArrayList<Integer>> lennot;
	private static HashMap<Integer, ArrayList<Integer>> lentohinnat;
	private static HashMap<Integer, Long> kaydytKaupungit;
	private static HashMap<Integer, Long> kaydytKaupungitIlmainen;
	private static IO io;
	
	public static void laskeHalvin(int kohde, int lentoMaara) {
		//long t = System.currentTimeMillis();
		//System.out.println("alkaa");

		kaydytKaupungit = new HashMap<Integer, Long>();
		kaydytKaupungitIlmainen = new HashMap<Integer, Long>();
		kaydytKaupungit.put(1, (long) 0);
		long hinta = laskeReitti2(1, kohde, lentoMaara, 0, -1, false);
		//System.out.println("aika: " + (System.currentTimeMillis()-t));
		io.print(hinta);		
	}
	
	public static long laskeReitti2(int kaupunki, int kohde, int lentoMaara, long hinta, long matalinHinta, boolean ilmainen) {
		if ((hinta >= matalinHinta && matalinHinta != -1) || kaupunki == kohde) {
			//System.out.println("kokonaishinta: " + hinta);
			return hinta;
		}
	
		long halvin = matalinHinta;
		//ArrayList<Integer> lennot1 = lennot.get(kaupunki);
		//ArrayList<Integer> lentohinnat1 = lentohinnat.get(kaupunki);
		

		for (int i = 0; i<lennot.get(kaupunki).size(); i++) {

			
			int uusikaupunki = lennot.get(kaupunki).get(i);
			long kokonaishinta = hinta;
			if (!ilmainen) {
				kokonaishinta += lentohinnat.get(kaupunki).get(i);
			
			if (kaydytKaupungitIlmainen.containsKey(uusikaupunki)) {
				if (kaydytKaupungitIlmainen.get(uusikaupunki) <= kokonaishinta)
					continue;
			}
			kaydytKaupungitIlmainen.put(uusikaupunki, kokonaishinta);
			}
			else {
				
				if (kaydytKaupungit.containsKey(uusikaupunki)) {
					if (kaydytKaupungit.get(uusikaupunki) <= kokonaishinta) {
						continue;
					}
					kaydytKaupungit.put(uusikaupunki, kokonaishinta);
				}
				
			}
			
			
			long halvinReitilla = laskeReitti2(uusikaupunki, kohde, lentoMaara, kokonaishinta, halvin, !ilmainen);
			//System.out.println("kaupungista: " + kaupunki + ", kaupunkiin: " + uusikaupunki + ", hinta: " + kokonaishinta);
			if (halvinReitilla < halvin || halvin == -1)
				halvin = halvinReitilla;
		}
		
		return halvin;
		
	}

	

	
	public static void main(String[] args) {
		
		io = new IO();
		
		lennot = new HashMap<Integer, ArrayList<Integer>>();
		lentohinnat = new HashMap<Integer, ArrayList<Integer>>();
		
		
		int kaupunkiMaara = io.nextInt();
		int lentoMaara = io.nextInt();
		
	//	int kaupunkiMaara = 5000;
		//int lentoMaara = 10000;
		
		for (int i = 1; i<=kaupunkiMaara; i++) {
			lennot.put(i, new ArrayList<Integer>());
			lentohinnat.put(i, new ArrayList<Integer>());
		}

		
		for (int i = 0; i<lentoMaara; i++) {
			int lahto = io.nextInt();
			int kohde = io.nextInt();
			int hinta = io.nextInt();
			
			lennot.get(lahto).add(kohde);
			lentohinnat.get(lahto).add(hinta);
		}
		
		
		
		
		/**
		int[] yhteys1 = {1, 2, 4};
		int[] yhteys2 = {1, 3, 7};
		int[] yhteys3 = {1, 4, 3};
		int[] yhteys4 = {1, 2, 3};
		int[] yhteys5 = {1, 3, 4};
		int[] yhteys6 = {2, 5, 5};
		int[] yhteys7 = {3, 5, 5};
		int[] yhteys8 = {5, 2, 6};
		int[] yhteys9 = {5, 4, 6};
		int[] yhteys10 = {5, 6, 6};
		
		yhteydet.add(yhteys1);
		yhteydet.add(yhteys2);
		yhteydet.add(yhteys3);
		yhteydet.add(yhteys4);
		yhteydet.add(yhteys5);
		yhteydet.add(yhteys6);
		yhteydet.add(yhteys7);
		yhteydet.add(yhteys8);
		yhteydet.add(yhteys9);
		yhteydet.add(yhteys10);
		*/
		//luoSatunnaisetYhteydet(kaupunkiMaara, lentoMaara);
	//	for (int i = 0; i<yhteydet.size(); i++) {
		//	int[] yhteys = yhteydet.get(i);
		//	System.out.println(yhteys[0] + "-->" + yhteys[1] + ", " + yhteys[2]);
	//	}
		
		
		laskeHalvin(kaupunkiMaara, lentoMaara);
		
		io.close();
	}
	
	public static ArrayList<int[]> luoSatunnaisetYhteydet(int kaupunkiMaara, int lentoMaara) {
		ArrayList<int[]> yhteydet = new ArrayList<int[]>();
		Random r = new Random();
		for (int i = 0; i<lentoMaara; i++) {
			int lahto = r.nextInt(kaupunkiMaara)+1;
			int kohde = r.nextInt(kaupunkiMaara)+1;
			int hinta = r.nextInt(100)+1;
			if (i == 0)
				lahto = 1;
			if (i == lentoMaara-1)
				kohde = kaupunkiMaara;
			
			if (lahto == kohde)
				lahto += 1;
			if (lahto >= kaupunkiMaara)
				lahto -= 2;
			int[] lisattava = {lahto, kohde, hinta};
			lennot.get(lahto).add(kohde);
			lentohinnat.get(lahto).add(hinta);
			
			
			
			yhteydet.add(lisattava);
		}
		
		for (int i = 1; i<kaupunkiMaara; i++) {
			if (lennot.get(i) != null)
			System.out.println(lennot.get(i).size());
		}
		return yhteydet;
	}

}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED