# UVa 10356

{{subst:Problem}}

## Summary

Dijkstra algorithm

## Explanation

1) Dijkstra algorithm after some adjustment of a graph.
2) Create such a graph that for every junction(vertex) will create a vertex from which is a street taken with a bike taken on his back and another vertex which from is street taken riding a bike
3) Run dijkstra - Dijkstra(start, end) with Dijkstra(V0, Vn-1)
4) Hint: Vertexes(junctions)

```                            v(0)...v(n-1) are for vertexes from which is bike taken on his back
v(n)...v(2n-1) are for vertexes from which is bike ridden
```

5) For every path from v(a)<--->v(b) create 4 paths in a graph

```                                 v(a)->v(b+n)
v(b+n)->v(a)
v(b)->v(a+n)
v(a+n)->v(b)

```

## Solution

```import java.util.*;
import java.io.*;

class Main {
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out, true);
int set = 0;
while (in.hasNextInt()) {
set++;
out.println("Set #" + set);

int n = in.nextInt();
int m = in.nextInt();

List<Node> nodeList = new ArrayList<Node>();
for (int i = 0; i < 2 * n; i++) {
Node node = new Node(i);
}

for (int i = 0; i < m; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();

Node nodeA = nodeList.get(a);
Node nodeAN = nodeList.get(a + n);
Node nodeB = nodeList.get(b);
Node nodeBN = nodeList.get(b + n);

Edge e1 = new Edge(nodeA, nodeBN, c);
Edge e2 = new Edge(nodeBN, nodeA, c);
Edge e3 = new Edge(nodeAN, nodeB, c);
Edge e4 = new Edge(nodeB, nodeAN, c);

}

PriorityQueue<Node> queue = new PriorityQueue<Node>(2*n, new NodeComparator());
Node startNode = nodeList.get(0);
startNode.setCurrentCost(0);

for (int i = 1; i < 2 * n; i++) {
}

while (!queue.isEmpty()) {
Node currentNode = queue.remove();
List<Edge> edges = currentNode.getEdges();
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);

Node start = e.getStart();
Node end = e.getEnd();
int cost = e.getCost();

// relaxation
if (start.getCurrentCost() != -1 && (end.getCurrentCost() == -1 || (end.getCurrentCost() > start.getCurrentCost() + cost))) {
queue.remove(end);
end.setCurrentCost(start.getCurrentCost() + cost);
end.setPreviousNode(start);
}
}
}

Node target = nodeList.get(n - 1);
int currentCost = target.getCurrentCost();
if (currentCost == -1) {
out.println("?");
} else {
out.println(currentCost);
}
}

out.flush();
out.close();

}
}

class Edge {
private Node start;
private Node end;
private int cost;

public Edge(Node start, Node end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}

public Node getStart() {
return start;
}

public Node getEnd() {
return end;
}

public int getCost() {
return cost;
}
}

class Node {
private int n;
private List<Edge> edges = new ArrayList<Edge>();

private int currentCost = -1;
private Node previousNode;

public Node(int n) {
this.n = n;
}

}

public List<Edge> getEdges() {
return edges;
}

public int getCurrentCost() {
return currentCost;
}

public void setCurrentCost(int currentCost) {
this.currentCost = currentCost;
}

public Node getPreviousNode() {
return previousNode;
}

public void setPreviousNode(Node previousNode) {
this.previousNode = previousNode;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + n;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (n != other.n)
return false;
return true;
}

}

class NodeComparator implements Comparator<Node> {

public int compare(Node o1, Node o2) {
if (o1.getCurrentCost() == o2.getCurrentCost()) {
return 0;
} else if (o1.getCurrentCost() == -1) {
return 1;
} else if (o2.getCurrentCost() == -1) {
return -1;
} else if (o1.getCurrentCost() < o2.getCurrentCost()) {
return -1;
} else if (o1.getCurrentCost() > o2.getCurrentCost()) {
return 1;
}
return 0;
}

}
```

## References

1. Reference 1

Categories here, use the form [[Category:UVa Online Judge|10356]] [[Category: Category Name]], see Categories for a list