Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Градови Problem 3 (0 / 3)
- Дадена е една мапа со еднонасочни патишта меѓу N градови во Македонија. За секој пат се знае должината на патот, почетниот и крајниот град. Да се најде вкупната должина на минималниот пат од еден до друг град и назад, и да се испечатат патеките со градовите низ кои треба да се помине напред и во обратен правец.
- Мапата со патишта е претставена како насочен тежински граф. Во првиот ред од влезот е даден број на градови N. Во вториот ред од влезот е даден бројот на насочени патишта. Во следните редови се дадени патиштата во облик: реден број на почетниот град, име на почетниот град, реден број на крајниот град, име на крајниот град, должина на патот. Во последните два реда се дадени имињата на градовите меѓу кои треба да се најде најкраткиот пат.
- Во првиот ред од излезот треба да се испечатат градовите низ кои треба да се помине за да се стигне по минимален пат од почетниот до крајниот град, а во вториот ред градовите низ кои треба да се помина за минималниот пат назад. Во последниот ред од излезот треба да се испечати должината на вкупниот минимален пат во двата правци.
- ========================================================================================================================================
- import com.sun.jmx.remote.internal.ArrayQueue;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- import java.util.Iterator;
- class Edge{
- private int fromVertex, toVertex;
- private float weight;
- public Edge(int from, int to, float weight){
- this.fromVertex = from;
- this.toVertex = to;
- this.weight = weight;
- }
- public int getFrom(){
- return this.fromVertex;
- }
- public int getTo(){
- return this.toVertex;
- }
- public float getWeight(){
- return this.weight;
- }
- }
- class Graph<E> {
- int num_nodes;
- GraphNode<E> adjList[];
- @SuppressWarnings("unchecked")
- public Graph(int num_nodes, E[] list) {
- this.num_nodes = num_nodes;
- adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- adjList[i] = new GraphNode<E>(i, list[i]);
- }
- @SuppressWarnings("unchecked")
- public Graph(int num_nodes) {
- this.num_nodes = num_nodes;
- adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- adjList[i] = new GraphNode<E>(i, null);
- }
- int adjacent(int x, int y) {
- // proveruva dali ima vrska od jazelot so
- // indeks x do jazelot so indeks y
- return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
- }
- void addEdge(int x, int y, float tezina) {
- // dodava vrska od jazelot so indeks x do jazelot so indeks y so tezina
- if (adjList[x].containsNeighbor(adjList[y])) {
- adjList[x].updateNeighborWeight(adjList[y], tezina);
- } else
- adjList[x].addNeighbor(adjList[y], tezina);
- }
- void deleteEdge(int x, int y) {
- adjList[x].removeNeighbor(adjList[y]);
- }
- /*************************** KRUSKAL ***********************************************************************/
- // Metoda koja generira niza od site rebra vo grafot
- public Edge[] getAllEdges() {
- int totalEdges = 0;
- for (int i = 0; i < this.num_nodes; i++) {
- // za sekoe teme go dodavame brojot na sosedi koi gi ima
- totalEdges += this.adjList[i].getNeighbors().size();
- }
- // System.out.println("METODA: Imame vk "+totalEdges+" rebra");
- Edge[] edges = new Edge[totalEdges];
- int index = 0;
- for (int i = 0; i < this.num_nodes; i++) {
- for (int j = 0; j < this.adjList[i].getNeighbors().size(); j++) {
- int index1 = this.adjList[i].getIndex();
- // se zemaat indeksot i tezinata na j-ot sosed na temeto i
- int index2 = this.adjList[i].getNeighbors().get(j).node
- .getIndex();
- float weight = this.adjList[i].getNeighbors().get(j).weight;
- edges[index++] = new Edge(index1, index2, weight);
- }
- }
- return edges;
- }
- // Metoda koja gi sortira site rebra
- private Edge[] sortEdges(Edge[] edges) {
- for (int i = 0; i < edges.length - 1; i++) {
- for (int j = i + 1; j < edges.length; j++) {
- if (edges[i].getWeight() > edges[j].getWeight()) {
- Edge tmp = edges[i];
- edges[i] = edges[j];
- edges[j] = tmp;
- }
- }
- }
- return edges;
- }
- // Metoda koja pravi unija na dve drva
- private int[] union(int u, int v, int[] vrski) {
- int findWhat, replaceWith;
- if (u < v) {
- findWhat = vrski[v];
- replaceWith = vrski[u];
- } else {
- findWhat = vrski[u];
- replaceWith = vrski[v];
- }
- // za dvete poddrva stava ist index
- // t.e. gi spojuva
- for (int i = 0; i < vrski.length; i++) {
- if (vrski[i] == findWhat) {
- vrski[i] = replaceWith;
- }
- }
- return vrski;
- }
- List<Edge> kruskal() {
- /*
- * Pomoshna niza za sledenje na kreiranite drva Ako dve teminja se del
- * od isto poddrvo togash imaat ista vrednost vo nizata
- */
- int vrski[] = new int[this.num_nodes];
- // niza koja gi sodrzi site rebra
- Edge[] edges = this.getAllEdges();
- // se sortiraat rebrata spored tezinite vo neopagjacki redosled
- edges = this.sortEdges(edges);
- // inicijalizacija na pomosnata niza za evidencija,
- // sekoj jazel si e posebno drvo
- for (int i = 0; i < this.num_nodes; i++)
- vrski[i] = i;
- // lista koja kje gi sodrzi MST rebra
- List<Edge> mstEdges = new ArrayList<Edge>();
- for (int i = 0; i < edges.length; i++) {
- // za sekoe rebro vo sortiran redosled
- Edge e = edges[i];
- if (vrski[e.getFrom()] != vrski[e.getTo()]) {
- // ako teminjata na ova rebro ne se vo isto poddrvo
- // ova rebro e MST rebro
- mstEdges.add(e);
- // sega dvete teminja treba da se vo isto poddrvo
- // t.e se pravi merge (unija) t.s. vo nizata vrski
- // za site elementi od dvete poddrva
- // go setira istiot (najmal) element od dvete poddrva
- vrski = this.union(e.getFrom(), e.getTo(), vrski);
- }
- // ako sme dodale num_nodes-1 rebra moze da prestaneme
- if (mstEdges.size() == (this.num_nodes - 1))
- break;
- }
- return mstEdges;
- }
- public void dfsVisit(boolean visited[], GraphNode<E> node, int end_node, float currCost, float[] dist, Stack<Integer> stack, Hashtable<Integer, String> ht){
- if(!visited[node.getIndex()] && node.getIndex() == end_node){
- // prevrti
- Stack<Integer> s = new Stack<Integer>();
- s.push(node.getIndex());
- while(!stack.isEmpty()){
- s.push(stack.pop());
- }
- // printaj
- while(!s.isEmpty()){
- System.out.print(ht.get(s.pop()) + " ");
- }
- return;
- }
- if(!visited[node.getIndex()]){
- visited[node.getIndex()] = true;
- stack.push(node.getIndex());
- LinkedList<GraphNodeNeighbor<E>> neigh = adjList[node.getIndex()].getNeighbors();
- for(int i = 0; i < neigh.size(); i++){
- GraphNode<E> node1= neigh.get(i).node;
- float weight = neigh.get(i).weight;
- if(!visited[node1.getIndex()] && currCost + weight <= dist[end_node]){
- dfsVisit(visited,node1,end_node, currCost + weight, dist, stack, ht);
- }
- }
- if(!stack.isEmpty())
- stack.pop();
- }
- }
- public void printPath(Hashtable<Integer,String> ht, int start_node, int end_node){
- boolean visited[] = new boolean[this.num_nodes];
- for(int i = 0; i < this.num_nodes; i++){
- visited[i] = false;
- }
- float dist[] = dijkstra(start_node);
- Stack<Integer> stek = new Stack<>();
- stek.push(start_node);
- LinkedList<GraphNodeNeighbor<E>> index = adjList[start_node].getNeighbors();
- for(int i = 0; i < index.size(); i++){
- GraphNode<E> node = index.get(i).node;
- float weight = index.get(i).weight;
- if(!visited[node.getIndex()] && weight <= dist[end_node]){
- dfsVisit(visited,node, end_node, weight, dist, stek, ht);
- }
- }
- }
- /*******************************************************************************************************/
- /************************ PRIM **************************************************************************/
- // Metoda koja go naogja najmaloto rebro do
- // teme na neposeten sosed
- private Edge getMinimalEdge(boolean[] included) {
- int index1 = Integer.MAX_VALUE, index2 = Integer.MAX_VALUE;
- float minweight = Float.MAX_VALUE;
- for (int i = 0; i < this.num_nodes; i++) {
- if (included[i]) {
- // ako e vkluceno temeto i
- // izmini gi negovite nevkluceni sosedi
- Iterator<GraphNodeNeighbor<E>> it = adjList[i].getNeighbors()
- .iterator();
- while (it.hasNext()) {
- GraphNodeNeighbor<E> pom = it.next();
- // ako sosedot ne e poseten i ima do sega najmala tezina
- if (!included[pom.node.getIndex()]
- && pom.weight < minweight) {
- index1 = i;
- index2 = pom.node.getIndex();
- minweight = pom.weight;
- }
- }
- }
- }
- if (minweight < Float.MAX_VALUE) {
- Edge ret = new Edge(index1, index2, minweight);
- return ret;
- }
- return null;
- }
- List<Edge> prim(int start_index) {
- // lista koja kje gi sodrzi MST rebra
- List<Edge> mstEdges = new ArrayList<Edge>();
- boolean included[] = new boolean[this.num_nodes];
- for (int i = 0; i < this.num_nodes; i++)
- included[i] = false;
- included[start_index] = true;
- for (int i = 0; i < this.num_nodes - 1; i++) {
- Edge e = this.getMinimalEdge(included);
- if (e == null) {
- System.out.println("Ne mozat da se povrzat site jazli");
- break;
- }
- included[e.getFrom()] = included[e.getTo()] = true;
- mstEdges.add(e);
- }
- return mstEdges;
- }
- /*******************************************************************************************************/
- /***************** DIJKSTRA ******************************************************************************/
- float[] dijkstra(int from) {
- /* Minimalna cena do sekoj od teminjata */
- float distance[] = new float[this.num_nodes];
- /* dali za temeto e najdena konecnata (minimalna) cena */
- boolean finalno[] = new boolean[this.num_nodes];
- for (int i = 0; i < this.num_nodes; i++) {
- distance[i] = -1;
- finalno[i] = false;
- }
- finalno[from] = true;
- distance[from] = 0;
- /*
- * vo sekoj cekor za edno teme se dobiva konecna minimalna cena
- */
- for (int i = 1; i < this.num_nodes; i++) {
- /* za site sledbenici na from presmetaj ja cenata */
- Iterator<GraphNodeNeighbor<E>> it = adjList[from].getNeighbors()
- .iterator();
- while (it.hasNext()) {
- GraphNodeNeighbor<E> pom = it.next();
- /* ako grankata kon sosedot nema konecna cena */
- if (!finalno[pom.node.getIndex()]) {
- /* ako ne e presmetana cena za temeto */
- if (distance[pom.node.getIndex()] <= 0) {
- distance[pom.node.getIndex()] = distance[from]
- + pom.weight;
- }
- /* inaku, ako e pronajdena poniska */
- else if (distance[from] + pom.weight < distance[pom.node
- .getIndex()]) {
- distance[pom.node.getIndex()] = distance[from]
- + pom.weight;
- }
- }
- }
- /* najdi teme so min. cena koja ne e konecna */
- boolean minit = false; /* min. ne e inicijaliziran */
- int k = -1;
- float minc = -1;
- /* proveri gi site teminja */
- for (int j = 0; j < this.num_nodes; j++) {
- if (!finalno[j] && distance[j] != -1) { /*ako cenata ne e konecna*/
- if (!minit) { /* ako ne e inicijaliziran minimumot */
- minc = distance[k = j]; /* proglasi go ova e minimum */
- minit = true; /* oznaci deka min e inicijaliziran */
- }
- /* proveri dali e pronajdeno teme so pomala cena */
- else if (minc > distance[j] && distance[j] > 0)
- minc = distance[k = j];
- }
- }
- finalno[from = k] = true;
- }
- return distance;
- }
- /*******************************************************************************************************/
- @Override
- public String toString() {
- String ret = new String();
- for (int i = 0; i < this.num_nodes; i++)
- ret += adjList[i] + "\n";
- return ret;
- }
- }
- class GraphNode<E> {
- private int index; //index (reden broj) na temeto vo grafot
- private E info;
- private LinkedList<GraphNodeNeighbor<E>> neighbors;
- public GraphNode(int index, E info) {
- this.index = index;
- this.info = info;
- neighbors = new LinkedList<GraphNodeNeighbor<E>>();
- }
- public boolean containsNeighbor(GraphNode<E> o){
- GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
- return neighbors.contains(pom);
- }
- public void addNeighbor(GraphNode<E> o, float weight){
- GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,weight);
- neighbors.add(pom);
- }
- public void removeNeighbor(GraphNode<E> o){
- GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
- if(neighbors.contains(pom))
- neighbors.remove(pom);
- }
- @Override
- public String toString() {
- String ret= "INFO:"+info+" SOSEDI:";
- for(int i=0;i<neighbors.size();i++)
- ret+="("+neighbors.get(i).node.info+","+neighbors.get(i).weight+") ";
- return ret;
- }
- public void updateNeighborWeight(GraphNode<E> o, float weight){
- Iterator<GraphNodeNeighbor<E>> i = neighbors.iterator();
- while(i.hasNext()){
- GraphNodeNeighbor<E> pom = i.next();
- if(pom.node.equals(o))
- pom.weight = weight;
- }
- }
- @Override
- public boolean equals(Object obj) {
- @SuppressWarnings("unchecked")
- GraphNode<E> pom = (GraphNode<E>)obj;
- return (pom.info.equals(this.info));
- }
- public int getIndex() {
- return index;
- }
- public void setIndex(int index) {
- this.index = index;
- }
- public E getInfo() {
- return info;
- }
- public void setInfo(E info) {
- this.info = info;
- }
- public LinkedList<GraphNodeNeighbor<E>> getNeighbors() {
- return neighbors;
- }
- public void setNeighbors(LinkedList<GraphNodeNeighbor<E>> neighbors) {
- this.neighbors = neighbors;
- }
- }
- class GraphNodeNeighbor<E> {
- GraphNode<E> node;
- float weight;
- public GraphNodeNeighbor(GraphNode<E> node, float weight) {
- this.node = node;
- this.weight = weight;
- }
- public GraphNodeNeighbor(GraphNode<E> node) {
- this.node = node;
- this.weight = 0;
- }
- @Override
- public boolean equals(Object obj) {
- @SuppressWarnings("unchecked")
- GraphNodeNeighbor<E> pom = (GraphNodeNeighbor<E>)obj;
- return pom.node.equals(this.node);
- }
- }
- public class Cities {
- public static void main(String []args) throws IOException {
- BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- int n = Integer.parseInt(in.readLine());
- int num_edges = Integer.parseInt(in.readLine());
- Hashtable<String, Integer> gradovi = new Hashtable<>(n+1);
- Hashtable< Integer, String > reverse = new Hashtable<>(n+1);
- Graph<Integer> g = new Graph<>(n);
- for(int i = 0; i < num_edges; i++){
- String line = in.readLine();
- String pom[] = line.split(" ");
- int index1 = Integer.parseInt(pom[0]);
- int index2 = Integer.parseInt(pom[2]);
- String grad1 = pom[1];
- String grad2 = pom[3];
- float dist = Float.parseFloat(pom[4]);
- if(!gradovi.contains(grad1)){
- gradovi.put(grad1,index1);
- reverse.put(index1,grad1);
- }
- if(!gradovi.contains(grad2)){
- gradovi.put(grad2,index2);
- reverse.put(index2,grad2);
- }
- g.adjList[index1].setInfo(index1);
- g.adjList[index2].setInfo(index2);
- g.addEdge(index1,index2,dist);
- }
- String grad1 = in.readLine();
- int index1 = gradovi.get(grad1);
- String grad2 = in.readLine();
- int index2 = gradovi.get(grad2);
- float sum = 0;
- float dijk1[] = g.dijkstra(index1);
- float dijk2[] = g.dijkstra(index2);
- sum += dijk1[index2];
- sum += dijk2[index1];
- g.printPath(reverse,index1, index2);
- System.out.println();
- g.printPath(reverse, index2, index1);
- System.out.println();
- System.out.println(sum);
- // todo: implement the function which prints the path
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement