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 int countOfGas;
- 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];
- for (int i = 0; i < M; i++) {
- int inM = Integer.parseInt(br.readLine());
- citiesHasGas[inM] = true; //mesto je pumpa
- countOfGas++;
- }
- edgeEndGas = new HashMap<>();
- gas = new HashMap[countOfGas];
- //JINAK NULL POITER EXCEPTION
- for(int i = 0; i < countOfCities;)
- {
- vertices[i] = new HashMap<>();
- gas[i] = new HashMap<>();
- }
- 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]);
- vertices[x].put(y, l);
- }
- // 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 = 0;
- for (int i = 0; i < countOfCities; i++) {
- if (!citiesHasGas[i]) {
- continue;
- } else {
- //zaciname jen z pump
- from = 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);
- citiesWeight[from] = 0;
- while (!dijkstraQ.isEmpty()) {
- //poll retrieves and remove element... u priority the lowest one
- int u = (int) dijkstraQ.poll();
- citiesVisited[u] = true; //visited
- // 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);
- if (length < citiesWeight[v] && length <= F) { //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
- // if (gas[counIndexOfpump] == null) {
- // gas[counIndexOfpump] = new HashMap<>();
- // }
- // gas[counIndexOfpump].put(v, length);
- dijkstraQ.remove(v);
- citiesWeight[v] = length;
- //prev[v] = u;
- dijkstraQ.add(v);
- }
- }
- }
- }
- }
- }
- public static int Dijkstra(int from) {
- // int[] prev = new int[countOfCities]; //nepotřebujem cestu, jen vahy, vzdalenosti
- //vsechny promenne znova instancujeme
- dijkstraQ = new PriorityQueue();
- citiesWeight = new int[countOfCities]; //index odpovida label vrcholu, weight
- citiesVisited = new boolean[countOfCities];
- dijkstraQ.add(from);
- citiesWeight[from] = 0;
- for (int j = 0; j < countOfCities; j++) {
- // if (i != from) {//zbytecne kontrola ifu, nastavim start zvlast
- citiesWeight[j] = Integer.MAX_VALUE;
- }
- citiesWeight[from] = 0;
- while (!dijkstraQ.isEmpty()) {
- int u = (int) dijkstraQ.poll();
- citiesVisited[u] = true; //visited
- // if(citiesWeight[u] == Integer.MAX) break; //nedostupny vrchol
- //pro kazdyho souseda v vrcholu u
- Set<Integer> keys = gas[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) gas[u].get(v);
- if (length < citiesWeight[v]) { //nastav novou dvahu pro v a jeho predka
- dijkstraQ.remove(v);
- citiesWeight[v] = length;
- //prev[v] = u;
- dijkstraQ.add(v);
- }
- }
- }
- }
- return citiesWeight[T];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement