Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package pal;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.HashMap;
- import java.util.PriorityQueue;
- import java.util.Queue;
- import java.util.Set;
- public class Main {
- //read
- static public int M; //countOfCities with gas station
- static public int N; //countOfCities without gas station
- static public int H; //highways
- static public int F; //max distance without refueling
- static public int S; //start label
- static public int T; //end label
- //create
- // static public int[][] highways; //matice sousednosti
- static public int[] citiesWeight; //index odpovida label hotelu - weight for dijkstra
- static public boolean[] citiesVisited; // for dijkstra
- static public boolean[] citiesHasGas;
- static public int countOfCities;
- static public Queue dijkstraQ; //fronta pro uchovavani navstivenych vrcholu pro Dijkstru
- //reprezentace grafu
- public static HashMap<Integer, Integer> edgeEnd; //vrchol V a delka hrany
- public static HashMap[] vertices; //vrchol U odpovida indexu pole
- public static HashMap<Integer, Integer> edgeEndGas;
- public static HashMap[] gas;
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- String[] in = br.readLine().split(" ");
- M = Integer.parseInt(in[0]);
- N = Integer.parseInt(in[1]);
- H = Integer.parseInt(in[2]);
- F = Integer.parseInt(in[3]);
- S = Integer.parseInt(in[4]);
- T = Integer.parseInt(in[5]);
- countOfCities = M + N;
- // highways = new int[countOfCities][countOfCities]; //matice
- edgeEnd = new HashMap<>();
- vertices = new HashMap[countOfCities];
- citiesHasGas = new boolean[countOfCities];
- edgeEndGas = new HashMap<>();
- /////////NEVIM, JAK PORESIT TO, ABY NEMUSELO MIT COUNT OF CITIES VELIKOST
- /////////PROTOZE PAK BY MI INDEX POLE NEODPOVIDAL LABEL VRCHOLU...
- gas = new HashMap[countOfCities];
- /////////
- for (int i = 0; i < M; i++) {
- int inM = Integer.parseInt(br.readLine());
- citiesHasGas[inM] = true; //mesto je pumpa
- }
- //mozna udelat for na vertices[x] = new HashMap<>(); a gas = new... jinak null pointer?
- for (int i = 0; i < H; i++) {
- String[] inH = br.readLine().split(" ");
- int x = Integer.parseInt(inH[0]); //x
- int y = Integer.parseInt(inH[1]); //y
- int l = Integer.parseInt(inH[2]); //l
- //mozna nebude potřeba predchozi for nyni?
- if (vertices[x] == null) {
- vertices[x] = new HashMap<>();
- }
- if (vertices[y] == null) {
- vertices[y] = new HashMap<>();
- }
- vertices[x].put(y, l);
- vertices[y].put(x, l);
- gas[x] = new HashMap<>();
- gas[y] = new HashMap<>();
- }
- DijkstraCreateNewGraph(S);
- int lengthEnd = Dijkstra(S);
- System.out.println(lengthEnd);
- }
- public static void DijkstraCreateNewGraph(int from) {
- // int[] prev = new int[countOfCities]; //nepotřebujem cestu, jen vahy, vzdalenosti
- dijkstraQ = new PriorityQueue();
- citiesWeight = new int[countOfCities]; //index odpovida label vrcholu, weight
- citiesVisited = new boolean[countOfCities];
- int counIndexOfpump = -1; //INDEXUJEME OD NULY...
- for (int i = 0; i < countOfCities; i++) {
- if (!citiesHasGas[i]) {
- continue;
- } else {
- //zaciname jen z pump
- from = i;
- System.out.println(i);
- counIndexOfpump++;
- }
- for (int j = 0; j < countOfCities; j++) {
- // if (i != from) {//zbytecne kontrola ifu, nastavim start zvlast
- citiesWeight[j] = Integer.MAX_VALUE;
- }
- citiesWeight[from] = 0;
- dijkstraQ.add(from);
- while (!dijkstraQ.isEmpty()) {
- //poll retrieves and remove element... u priority the lowest one
- int u = (int) dijkstraQ.poll();
- citiesVisited[u] = true; //visited
- //
- dijkstraQ.remove(u);
- // if(citiesWeight[u] == Integer.MAX) break; //nedostupny vrchol
- //pro kazdyho souseda v vrcholu u
- Set<Integer> keys = vertices[u].keySet();
- for (Integer v : keys) {//jestli soused v nebyl navstiven
- if (citiesVisited[v] == false) {//spocitej help = citiesWeight[u] + delka mezi uv
- int length = citiesWeight[u] + (int) vertices[u].get(v);
- // System.out.println("pred kontrolou " + u + " a " + v + " delka " + length);
- if (length < citiesWeight[v] && length <= F && citiesHasGas[v]) { //nastav novou dvahu pro v a jeho predka, pokud staci delka paliva na cestu mezi pumpama
- // u a v pumpy, pridej je do noveho redukovaneho grafu
- gas[u].put(v, length);
- System.out.println(gas[u]);
- citiesWeight[v] = length;
- //prev[v] = u;
- }
- }
- }
- }
- }
- }
- public static int Dijkstra(int from) {
- // int[] prev = new int[countOfCities]; //nepotřebujem cestu, jen vahy, vzdalenosti
- //vsechny promenne znova instancujeme
- dijkstraQ = new PriorityQueue();
- //vetsi pole, ale index odovida labelu vrcholu... jinak bych musela v tom poli hledat nejak, tak nevim, co s tim?
- citiesWeight = new int[countOfCities]; //index odpovida label vrcholu, weight
- citiesVisited = new boolean[countOfCities];
- for (int j = 0; j < countOfCities; j++) {
- citiesWeight[j] = Integer.MAX_VALUE;
- }
- citiesWeight[from] = 0;
- dijkstraQ.add(from);
- while (!dijkstraQ.isEmpty()) {
- int u = (int) dijkstraQ.poll();
- citiesVisited[u] = true; //visited
- // System.out.println(u);
- dijkstraQ.remove(u);
- // if(citiesWeight[u] == Integer.MAX) break; //nedostupny vrchol
- //pro kazdyho souseda v vrcholu u
- Set<Integer> keys = gas[u].keySet();
- System.out.println(keys);
- for (Integer v : keys) {//jestli soused v nebyl navstiven
- if (citiesVisited[v] == false) {//spocitej help = citiesWeight[u] + delka mezi uv
- int length = citiesWeight[u] + (int) gas[u].get(v);
- //// System.out.println("pred kontrolou " + u + " a " + v + " delka " + length);
- ///////TENHLE DIJKSTRA NEJAK NEFUNGUJE///////
- if (length < citiesWeight[v]) { //nastav novou dvahu pro v a jeho predka
- citiesWeight[v] = length;
- //prev[v] = u;
- dijkstraQ.add(v);
- }
- }
- }
- }
- return citiesWeight[T];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement