import java.util.*;
public class Main {
static final int INF
= Integer.
MAX_VALUE;
public static int shortestPath(int[][] graph, int n) {
int[] cost = new int[n];
int[] path = new int[n];
cost[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
cost[i] = INF;
for (int j = i + 1; j < n; j++) {
if (graph[i][j] != 0 && cost[i] > graph[i][j] + cost[j]) {
cost[i] = graph[i][j] + cost[j];
path[i] = j;
}
}
}
System.
out.
print("Shortest Path: "); int i = 0;
while (i != n - 1) {
i = path[i];
}
return cost[0];
}
public static void main
(String[] args
) { int[][] graph = {
// 0 1 2 3 4 5 6 7
{ 0, 1, 2, 5, 0, 0, 0, 0 }, // 0
{ 0, 0, 0, 0, 4, 11, 0, 0 }, // 1
{ 0, 0, 0, 0, 9, 5, 16, 0 }, // 2
{ 0, 0, 0, 0, 0, 0, 2, 0 }, // 3
{ 0, 0, 0, 0, 0, 0, 0, 18 }, // 4
{ 0, 0, 0, 0, 0, 0, 0, 13 }, // 5
{ 0, 0, 0, 0, 0, 0, 0, 2 }, // 6
{ 0, 0, 0, 0, 0, 0, 0, 0 } // 7 (destination)
};
int n = graph.length;
int cost = shortestPath(graph, n);
System.
out.
println("Minimum Cost: " + cost
); }
}
aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgc3RhdGljIGZpbmFsIGludCBJTkYgPSBJbnRlZ2VyLk1BWF9WQUxVRTsKCiAgICBwdWJsaWMgc3RhdGljIGludCBzaG9ydGVzdFBhdGgoaW50W11bXSBncmFwaCwgaW50IG4pIHsKICAgICAgICBpbnRbXSBjb3N0ID0gbmV3IGludFtuXTsKICAgICAgICBpbnRbXSBwYXRoID0gbmV3IGludFtuXTsKCiAgICAgICAgY29zdFtuIC0gMV0gPSAwOwoKICAgICAgICBmb3IgKGludCBpID0gbiAtIDI7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgICAgIGNvc3RbaV0gPSBJTkY7CiAgICAgICAgICAgIGZvciAoaW50IGogPSBpICsgMTsgaiA8IG47IGorKykgewogICAgICAgICAgICAgICAgaWYgKGdyYXBoW2ldW2pdICE9IDAgJiYgY29zdFtpXSA+IGdyYXBoW2ldW2pdICsgY29zdFtqXSkgewogICAgICAgICAgICAgICAgICAgIGNvc3RbaV0gPSBncmFwaFtpXVtqXSArIGNvc3Rbal07CiAgICAgICAgICAgICAgICAgICAgcGF0aFtpXSA9IGo7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnQoIlNob3J0ZXN0IFBhdGg6ICIpOwogICAgICAgIGludCBpID0gMDsKICAgICAgICB3aGlsZSAoaSAhPSBuIC0gMSkgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KGkgKyAiIC0+ICIpOwogICAgICAgICAgICBpID0gcGF0aFtpXTsKICAgICAgICB9CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKG4gLSAxKTsKCiAgICAgICAgcmV0dXJuIGNvc3RbMF07CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludFtdW10gZ3JhcGggPSB7CiAgICAgICAgICAgIC8vIDAgIDEgIDIgIDMgIDQgIDUgIDYgIDcKICAgICAgICAgICAgeyAwLCAxLCAyLCA1LCAwLCAwLCAwLCAwIH0sIC8vIDAKICAgICAgICAgICAgeyAwLCAwLCAwLCAwLCA0LCAxMSwgMCwgMCB9LCAvLyAxCiAgICAgICAgICAgIHsgMCwgMCwgMCwgMCwgOSwgNSwgMTYsIDAgfSwgLy8gMgogICAgICAgICAgICB7IDAsIDAsIDAsIDAsIDAsIDAsIDIsIDAgfSwgLy8gMwogICAgICAgICAgICB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDE4IH0sIC8vIDQKICAgICAgICAgICAgeyAwLCAwLCAwLCAwLCAwLCAwLCAwLCAxMyB9LCAvLyA1CiAgICAgICAgICAgIHsgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMiB9LCAgLy8gNgogICAgICAgICAgICB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAgfSAgIC8vIDcgKGRlc3RpbmF0aW9uKQogICAgICAgIH07CgogICAgICAgIGludCBuID0gZ3JhcGgubGVuZ3RoOwogICAgICAgIGludCBjb3N0ID0gc2hvcnRlc3RQYXRoKGdyYXBoLCBuKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk1pbmltdW0gQ29zdDogIiArIGNvc3QpOwogICAgfQp9Cg==