func 특정한최단경로() {
/**
input start -----
*/
var input: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
let N: Int = input[0] // node 갯수
let E: Int = input[1] // edge 갯수
/**
그래프
i 인덱스에는 (to, distance) 형태로 저장
ex)
graph[i][0].to 는 i에서의 목적지
graph[i][0].cost 는 i에서 목적지까지의 거리
*/
var graph: [[(to: Int, cost: Int)]] = [[(Int, Int)]](repeating: [], count: N + 1)
for _ in 0..<E {
input = readLine()!.split(separator: " ").map { Int($0)! }
graph[input[0]].append((input[1], input[2]))
graph[input[1]].append((input[0], input[2]))
}
input = readLine()!.split(separator: " ").map { Int($0)! }
let v1: Int = input[0] // 경유 1
let v2: Int = input[1] // 경유 2
/**
----- input end
*/
var routes: [Int] = []
var distances: [[Int]] = [[Int]](repeating: [Int](repeating: 2_000_000_000, count: N + 1), count: N + 1)
var isVisited: [[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: N + 1), count: N + 1)
for i in 1...N {
distances[i][i] = 0
}
getShortestDistance(from: 1)
getShortestDistance(from: v1)
getShortestDistance(from: v2)
routes.append(distances[1][v1] + distances[v1][v2] + distances[v2][N])
routes.append(distances[1][v2] + distances[v2][v1] + distances[v1][N])
let result = routes.min()!
print("\(result > 0 && result < 2_000_000_000 ? result : -1)")
/**
1. (1 -> v1) + (v1 -> v2) + (v2 -> N)
2. (1 -> v2) + (v2 -> v1) + (v1 -> N)
*/
func getShortestDistance(from: Int) {
var now: Int
while true {
now = getMinIndex(from: from)
if now == 0 {
return
}
for connectedCity in graph[now] {
if connectedCity.cost + distances[from][now] < distances[from][connectedCity.to] {
distances[from][connectedCity.to] = connectedCity.cost + distances[from][now]
}
}
}
}
func getMinIndex(from: Int) -> Int {
var min: Int = Int.max
var minIndex: Int = 0
for i in 1...N {
if distances[from][i] < min && !isVisited[from][i] {
minIndex = i
min = distances[from][i]
}
}
isVisited[from][minIndex] = true
return minIndex
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//BOJ_1504_특정한 최단경로
class Main{
public static final int INF = 987654321;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken()); // 정점의 수
int E = Integer.parseInt(st.nextToken()); // 간선의 수
//간선 정보 리스트 배열 초기화
List<Edge> edges[] = new List[N+1];
for (int i = 1; i<=N; i++){
edges[i] = new ArrayList<>();
}
//간선 정보 입력
for (int i = 0; i<E; i++){
st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
edges[from].add(new Edge(to, cost)); // 무방향 그래프
edges[to].add(new Edge(from, cost));
}
//임의의 두 정점
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
System.out.println(findShortPath(u, v, N, edges));
br.close();
}
//두 정점을 지나는 경로 찾기
public static long findShortPath(int u, int v, int N, List<Edge> edges[]){
long p1 = 0; //1 - u - v - N;
long p2 = 0; //1 - v - n - N;
p1 += dijkstra(1, u, N, edges);
p1 += dijkstra(u, v, N, edges);
p1 += dijkstra(v, N, N, edges);
p2 += dijkstra(1, v, N, edges);
p2 += dijkstra(v, u, N, edges);
p2 += dijkstra(u, N, N, edges);
long ans = Math.min(p1, p2);
if (ans >= INF) return -1; //경로가 없는 경우
return ans;
}
//from 에서 to 까지의 최단 거리
public static long dijkstra(int from, int to, int N, List<Edge> edges[]){
PriorityQueue<Edge> pq = new PriorityQueue<>();
long[] distance = new long[N+1];
Arrays.fill(distance, INF);
distance[from] = 0;
pq.offer(new Edge(from, distance[from]));
while (!pq.isEmpty()){
Edge now = pq.poll();
if (now.to == to) return distance[to]; // 목적지 도달한 경우
for (Edge e : edges[now.to]){
if (distance[e.to] > distance[now.to] + e.cost){
distance[e.to] = distance[now.to] + e.cost;
pq.offer(new Edge(e.to, distance[e.to]));
}
}
}
return INF;
}
public static class Edge implements Comparable<Edge>{
int to;
long cost;
public Edge(int to, long cost){
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.cost, o.cost);
}
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class ShortPath {
static final int INF = 9876543;
static List<List<Node>> graph = new ArrayList<>();
static int N, E;
static int a, b, c;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
for(int i = 0; i < N + 1; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < E; i++){
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
st = new StringTokenizer(br.readLine());
int waypoint1 = Integer.parseInt(st.nextToken());
int waypoint2 = Integer.parseInt(st.nextToken());
long distance1 = dijkstra(1, waypoint1) + dijkstra(waypoint1, waypoint2) + dijkstra(waypoint2, N);
long distance2 = dijkstra(1, waypoint2) + dijkstra(waypoint2, waypoint1) + dijkstra(waypoint1, N);
long min = Math.min(distance1, distance2);
if(min >= INF){
System.out.println("-1");
}
else {
System.out.println(min);
}
}
public static long dijkstra(int start, int end){
PriorityQueue<Node> pq = new PriorityQueue<>();
long[] result = new long[N + 1];
boolean[] visited = new boolean[N + 1];
Arrays.fill(result, INF);
result[start] = 0;
pq.offer(new Node(start, 0));
while(!pq.isEmpty()){
Node node = pq.poll();
int idx = node.idx;
long dis = node.distance;
if(visited[idx]) {
continue;
}
visited[idx] = true;
for(Node n : graph.get(idx)) {
if (dis + n.distance < result[n.idx]) {
result[n.idx] = dis + n.distance;
pq.offer(new Node(n.idx, result[n.idx]));
}
}
}
return result[end];
}
}
class Node implements Comparable<Node>{
int idx;
long distance;
Node(int idx, long distance){
this.idx = idx;
this.distance = distance;
}
@Override
public int compareTo(Node o) {
return Long.compare(this.distance, o.distance);
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main_BOJ_1504_특정한최단경로_0704 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int max = 9876543;
int N = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int[][] map = new int[N][N];
int[] dist = new int[N];
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
map[i][j] = max;
}
}
for(int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken());
map[a][b] = map[b][a] = c;
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken())-1;
int v2 = Integer.parseInt(st.nextToken())-1;
// 1 -> v1 -> v2 -> N
int way1 = dijkstra(0, v1, map, dist, max, N)
+ dijkstra(v1, v2, map, dist, max, N)
+ dijkstra(v2, N-1, map, dist, max, N);
// 1 -> v2 -> v1 -> N
int way2 = dijkstra(0, v2, map, dist, max, N)
+ dijkstra(v2, v1, map, dist, max, N)
+ dijkstra(v1, N-1, map, dist, max, N);
int min = Math.min(way1, way2);
if(min>=max) {
System.out.println("-1");
} else {
System.out.println(min);
}
}
static int dijkstra(int start, int end, int[][] map, int[] dist, int max, int N) {
Arrays.fill(dist, max);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, dist[start]));
while(!pq.isEmpty()) {
Node cur = pq.poll();
int idx = cur.idx;
int cost = cur.cost;
if(cost > dist[idx]) continue;
for(int i=0; i<N; i++) {
if(map[idx][i] == max) continue;
if(dist[i] > dist[idx] + map[idx][i]) {
dist[i] = dist[idx] + map[idx][i];
pq.offer(new Node(i, dist[i]));
}
}
}
return dist[end];
}
static class Node implements Comparable<Node>{
int idx;
int cost;
public Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_1504 {
static int N, E;
static int[][] map;
static boolean flag;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
map = new int[N+1][N+1];
for(int i=1; i<=N; i++){
Arrays.fill(map[i], 987654321);
}
for(int i=0; i<E; i++){
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int dis = Integer.parseInt(st.nextToken());
if(map[from][to] != 987654321){
map[from][to] = Math.min(map[from][to], dis);
map[to][from] = map[from][to]; //양방향
}else{
map[from][to] = dis;
map[to][from] = dis;
}
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//1번에서 N번으로 이동할떄 V1, V2 무조건 지나가기
int distance = -1;
//경우1 : 1 -> v1 -> v2 -> N
int case1 = 0;
flag = false;
case1 += dijkstra(1, v1);
case1 += dijkstra(v1, v2);
case1 += dijkstra(v2, N);
if(flag){
case1 = 987654321;
}
//경우2 : 1 -> v2 -> v1 -> N
int case2 = 0;
flag = false;
case2 += dijkstra(1, v2);
case2 += dijkstra(v2, v1);
case2 += dijkstra(v1, N);
if(flag){
case2 = 987654321;
}
//경우3: 갈 수 있는 경우 없음
if(case1 != 987654321 || case2 != 987654321){
distance = Math.min(case1, case2);
}
System.out.println(distance);
}
public static int dijkstra(int start, int finish){
boolean[] visited = new boolean[N+1];
int[] dis = new int[N+1];
Arrays.fill(dis, 987654321);
dis[start] = 0;
for(int i=1; i<=N; i++){
int min = Integer.MAX_VALUE;
int current = 1;
for(int j=1; j<=N; j++){
if(!visited[j] && min > dis[j]){
min = dis[j];
current = j;
}
}
visited[current] = true;
for(int j=1; j<=N; j++){
if(!visited[j] && map[current][j] != -1 && dis[j] > dis[current] + map[current][j]){
dis[j] = dis[current] + map[current][j];
}
}
}
if(dis[finish] == 987654321){
flag = true;
}
return dis[finish];
}
}
/*
2 0
1 2
*/