25.最爱的城市

// dijkstra求最短路
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

int main() {
    int n, m;
    while (cin >> n >> m) {
        // 建图
        vector<vector<int>> g(n + 1, vector<int>(n + 1, inf));
        for (int i = 0; i < m; ++i) {
            int a, b, w;
            cin >> a >> b >> w;
            g[a][b] = min(g[a][b], w);
            g[b][a] = min(g[b][a], w);
        }
        
        int x, y;
        cin >> x >> y;
        
        vector<int> dist(n + 1, inf); // dist[i]: x->i的最短距离
        dist[x] = 0;
        vector<int> st(n + 1); // st[i]: dist[i]是否已经确定
        while (1) {
            // 找出还未确定最短路的点里面，距离x最近的点t
            int t = -1;
            for (int i = 1; i <= n; ++i) {
                if (!st[i] && (t == -1 || dist[i] < dist[t])) {
                    t = i;
                }
            }
            
            // 非连通或找到x->y的最短路了
            if (t == -1 || dist[t] == inf || st[t] || t == y) { 
                break;
            }
            st[t] = true;
            
            for (int i = 1; i <= n; ++i) {
                // 用dist[t]更新s到其它点的距离
                if (!st[i]) dist[i] = min(dist[i], dist[t] + g[t][i]);
            }
        }
        if (dist[y] >= inf) cout << "No path" << endl;
        else cout << dist[y] << endl;
    }
    
    return 0;
}

// 深度优先搜索
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int INF = 25; // 题目中描述城市距离最大是25

// 深度优先搜索
int dfs(int curr, int target, unordered_map<int, vector<pair<int, int>>>& graph, vector<bool>& visited) {
    if (curr == target) {
        return 0;
    }

    visited[curr] = true;
    int min_distance = INF; // C++里取最大数 

    for (const auto& neighbor : graph[curr]) {
        int next_city = neighbor.first;
        int edge_length = neighbor.second;

        if (!visited[next_city]) {
            int path_distance = dfs(next_city, target, graph, visited);
            if (path_distance != INF) {
                min_distance = min(min_distance, edge_length + path_distance);
            }
        }
    }

    visited[curr] = false;
    return min_distance;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        unordered_map<int, vector<pair<int, int>>> graph;
        // 构建图
        while (m--) {
            int a, b, l;
            std::cin >> a >> b >> l;
            graph[a].emplace_back(b, l);
            graph[b].emplace_back(a, l);
        }

        int x, y;
        std::cin >> x >> y;

        std::vector<bool> visited(n + 1, false);
        int shortest_distance = dfs(x, y, graph, visited);

        if (shortest_distance == INF) {
            cout << "No path" << endl;
        } else {
            cout << shortest_distance << endl;
        }
    }
    return 0;
}

// 方法三：Floyd-Warshall算法
#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));

        for (int i = 1; i <= n; i++) {
            dist[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            int a, b, l;
            cin >> a >> b >> l;
            dist[a][b] = l;
            dist[b][a] = l;
        }

        // Floyd-Warshall算法：通过k中转
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        int x, y;
        cin >> x >> y;

        if (dist[x][y] == INF) {
            cout << "No path" << endl;
        } else {
            cout << dist[x][y] << endl;
        }
    }

    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int citiNum = scanner.nextInt();
            int edgeNum = scanner.nextInt();
            //为了方便，索引0是无用的
            int[][] graph = new int[citiNum + 1][citiNum + 1];
            for (int i = 0; i < graph.length; i++) {
                int[] current = new int[citiNum + 1];
                Arrays.fill(current, Integer.MAX_VALUE);
                graph[i] = current;
            }
            for (int i = 0; i < edgeNum; i++) {
                int start = scanner.nextInt();
                int end = scanner.nextInt();
                int value = scanner.nextInt();
                graph[start][end] = Math.min(value, graph[start][end]);
                graph[end][start] = graph[start][end];
            }
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int[] isVisit = new int[citiNum + 1];
            int sum = 0;
            int res = dfs(graph, x, y, isVisit, sum);
            if (res != Integer.MAX_VALUE) {
                System.out.println(res);
            } else {
                System.out.println("No path");
            }
        }
    }

    private static int dfs(int[][] graph, int start, int end, int[] isVisit, int sum) {
        if (end == start) {
            return sum;
        }
        isVisit[start] = 1;
        int[] array = graph[start];
        //当前节点出发能到终点的最小值
        Integer min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != Integer.MAX_VALUE && isVisit[i] == 0) {
                // 从当前i节点出发
                isVisit[i] = 1;
                sum += array[i];
                int res = dfs(graph, i, end, isVisit, sum);
                if (res != Integer.MAX_VALUE) {
                    min = Math.min(min, res);
                }
                sum -= array[i];
                isVisit[i] = 0;
            }
        }
        return min;
    }
}

// 方法二：Floyd-Warshall算法
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();

            // dist[i][j]表示城市i到城市j的最短距离
            int[][] dist = new int[n + 1][n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j)
                        dist[i][j] = 0;
                    else
                        dist[i][j] = Integer.MAX_VALUE;
                }
            }

            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int l = sc.nextInt();
                dist[a][b] = l;
                dist[b][a] = l;
            }

            // Floyd-Warshall算法：通过k中转
            for (int k = 1; k <= n; k++) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE)
                            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }

            int x = sc.nextInt();
            int y = sc.nextInt();
            if (dist[x][y] == Integer.MAX_VALUE) {
                System.out.println("No path");
            } else {
                System.out.println(dist[x][y]);
            }
        }

        sc.close();
    }
}

// 方法三：dijkstra算法
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int n = sc.nextInt(); // 城市个数
            int m = sc.nextInt(); // 线段个数
            int[][] graph = new int[n + 1][n + 1]; // 二维数组表示城市之间的距离，初始为无穷大

            for (int i = 0; i <= n; i++) {
                Arrays.fill(graph[i], Integer.MAX_VALUE);
                graph[i][i] = 0; // 自己到自己的距离为0
            }

            // 读取每条线段的信息，更新城市之间的距离
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int l = sc.nextInt();
                graph[a][b] = l;
                graph[b][a] = l; // 因为是无向图，所以两个方向都要更新
            }

            int x = sc.nextInt(); // 起点城市
            int y = sc.nextInt(); // 终点城市

            int result = dijkstra(n, graph, x, y);
            if (result == Integer.MAX_VALUE)
                System.out.println("No path");
            else
                System.out.println(result);
        }

        sc.close();
    }

    /* 迪杰斯特拉算法求解最短距离 */
    private static int dijkstra(int n, int[][] graph, int x, int y) {
        boolean[] visited = new boolean[n + 1]; // 记录节点是否被访问过
        int[] dist = new int[n + 1]; // 记录起点到每个节点的最短距离，初始为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[x] = 0; // 起点到自己的距离为0

        for (int i = 1; i <= n; i++) {
            int u = -1;
            for (int v = 1; v <= n; v++) {
                if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
                    u = v; // 找出未访问节点中距离起点最近的节点
                }
            }

            visited[u] = true; // 将该节点标记为已访问

            for (int v = 1; v <= n; v++) {
                if (!visited[v] && graph[u][v] != Integer.MAX_VALUE) {
                    // 更新未访问节点的最短距离
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
                }
            }
        }

        return dist[y]; // 返回起点到终点的最短距离
    }
}

# 解法一：dijkstra算法
def dijkstra(n, m, edges, x, y):
    INF = float('inf')
    graph = [[INF] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        graph[i][i] = 0

    for a, b, l in edges:
        graph[a][b] = l
        graph[b][a] = l

    visited = [False] * (n + 1)
    dist = [INF] * (n + 1)
    dist[x] = 0

    for _ in range(n):
        min_dist = INF
        u = -1

        for v in range(1, n + 1):
            if not visited[v] and dist[v] < min_dist:
                min_dist = dist[v]
                u = v

        if u == -1:
            break

        visited[u] = True

        for v in range(1, n + 1):
            if not visited[v] and graph[u][v] != INF:
                dist[v] = min(dist[v], dist[u] + graph[u][v])

    if dist[y] == INF:
        return "No path"
    return dist[y]


def main():
    while True:
        try:
            n, m = map(int, input().split())
            edges = [tuple(map(int, input().split())) for _ in range(m)]
            x, y = map(int, input().split())

            result = dijkstra(n, m, edges, x, y)
            print(result)
        except EOFError:
            break


if __name__ == "__main__":
    main()

# 方法二：Floyd-Warshall算法
def main():
    while True:
        try:
            n, m = map(int, input().split())
            dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]

            for i in range(1, n + 1):
                dist[i][i] = 0

            for i in range(m):
                a, b, l = map(int, input().split())
                dist[a][b] = l
                dist[b][a] = l

            # Floyd-Warshall算法：通过k中转
            for k in range(1, n + 1):
                for i in range(1, n + 1):
                    for j in range(1, n + 1):
                        if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

            x, y = map(int, input().split())
            if dist[x][y] == float('inf'):
                print("No path")
            else:
                print(dist[x][y])

        except EOFError:
            break


if __name__ == "__main__":
    main()

# 方法三：dfs
def dfs(graph, visited, start, end, current_distance):
    if start == end:
        return current_distance

    visited[start] = True
    min_distance = float('inf')

    for neighbor, distance in graph[start]:
        if not visited[neighbor]:
            min_distance = min(min_distance, dfs(graph, visited, neighbor, end, current_distance + distance))

    visited[start] = False
    return min_distance


def main():
    while True:
        try:
            n, m = map(int, input().split())

            graph = {i: [] for i in range(1, n + 1)}

            for _ in range(m):
                a, b, l = map(int, input().split())
                graph[a].append((b, l))
                graph[b].append((a, l))

            x, y = map(int, input().split())

            visited = [False] * (n + 1)
            shortest_distance = dfs(graph, visited, x, y, 0)

            if shortest_distance == float('inf'):
                print("No path")
            else:
                print(shortest_distance)

        except EOFError:
            break


if __name__ == "__main__":
    main()

# 解法一：Floyd-Warshall算法
package main

import (
	"fmt"
	"math"
)

func floydWarshall(graph [][]int, n int) {
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
			}
		}
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	for {
		var n, m int
		if _, err := fmt.Scan(&n, &m); err != nil {
			break
		}

		graph := make([][]int, n)
		for i := 0; i < n; i++ {
			graph[i] = make([]int, n)
			for j := 0; j < n; j++ {
				if i == j {
					graph[i][j] = 0
				} else {
					graph[i][j] = math.MaxInt32
				}
			}
		}

		for i := 0; i < m; i++ {
			var a, b, l int
			fmt.Scan(&a, &b, &l)
			a--
			b--
			graph[a][b] = l
			graph[b][a] = l
		}

		floydWarshall(graph, n)

		var x, y int
		fmt.Scan(&x, &y)
		x--
		y--

		if graph[x][y] != math.MaxInt32 {
			fmt.Println(graph[x][y])
		} else {
			fmt.Println("No path")
		}
	}
}

# 解法二：Dijkstra算法
package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	to, cost int
}

type Item struct {
	node, dist int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Item))
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func dijkstra(graph [][]Edge, start int) []int {
	n := len(graph)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = 1<<31 - 1
	}
	dist[start] = 0

	pq := make(PriorityQueue, 0)
	heap.Push(&pq, &Item{node: start, dist: 0})

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		v := item.node
		if dist[v] < item.dist {
			continue
		}
		for _, edge := range graph[v] {
			if dist[edge.to] > dist[v]+edge.cost {
				dist[edge.to] = dist[v] + edge.cost
				heap.Push(&pq, &Item{node: edge.to, dist: dist[edge.to]})
			}
		}
	}

	return dist
}

func main() {
	var n, m int
	for {
		if _, err := fmt.Scan(&n, &m); err != nil {
			break
		}

		graph := make([][]Edge, n)
		for i := 0; i < m; i++ {
			var a, b, l int
			fmt.Scan(&a, &b, &l)
			a--
			b--
			graph[a] = append(graph[a], Edge{b, l})
			graph[b] = append(graph[b], Edge{a, l})
		}

		var x, y int
		fmt.Scan(&x, &y)
		x--
		y--

		dist := dijkstra(graph, x)
		if dist[y] != 1<<31-1 {
			fmt.Println(dist[y])
		} else {
			fmt.Println("No path")
		}
	}
}

# 解法三：DFS算法
package main

import (
	"fmt"
)

type Edge struct {
	to, cost int
}

func dfs(graph [][]Edge, visited []bool, u, dest, cost int, minCost *int) {
	if u == dest {
		if cost < *minCost {
			*minCost = cost
		}
		return
	}

	visited[u] = true
	for _, edge := range graph[u] {
		if !visited[edge.to] {
			dfs(graph, visited, edge.to, dest, cost+edge.cost, minCost)
		}
	}
	visited[u] = false
}

func main() {
	var n, m int
	for {
		if _, err := fmt.Scan(&n, &m); err != nil {
			break
		}

		graph := make([][]Edge, n)
		for i := 0; i < m; i++ {
			var a, b, l int
			fmt.Scan(&a, &b, &l)
			a--
			b--
			graph[a] = append(graph[a], Edge{b, l})
			graph[b] = append(graph[b], Edge{a, l})
		}

		var x, y int
		fmt.Scan(&x, &y)
		x--
		y--

		visited := make([]bool, n)
		minCost := 1<<31 - 1
		dfs(graph, visited, x, y, 0, &minCost)

		if minCost != 1<<31-1 {
			fmt.Println(minCost)
		} else {
			fmt.Println("No path")
		}
	}
}

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
let m, n
let input = []
rl.on('line', (line) => {
    input.push(line)
}).on('close', () => {
    let index = 0
    while(index < input.length) {
        const [n,m] = input[index++].split(' ').map(Number)
        const edges = []
        for(let i = 0; i < m; i++) {
            const [a,b,l] = input[index++].split(' ').map(Number)
            edges.push([a,b,l])
        }
        const [x,y] = input[index++].split(' ').map(Number)
        const result = floydWarshall(n,m,edges,x,y)
        if(result === INF) {
            console.log('No path')
        } else {
            console.log(result)
        }
    }
})

const INF = 1e9;

function floydWarshall(n, m, edges, x, y) {
  // 初始化距离矩阵
  const dist = [];
  for (let i = 0; i <= n; i++) {
    dist[i] = [];
    for (let j = 0; j <= n; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else {
        dist[i][j] = INF;
      }
    }
  }

  // 更新已知边的距离
  for (let i = 0; i < m; i++) {
    const [a, b, l] = edges[i];
    dist[a][b] = Math.min(dist[a][b], l);
    dist[b][a] = Math.min(dist[b][a], l);
  }

  // 使用 Floyd-Warshall 算法计算最短距离
  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  return dist[x][y];
}

#include <stdio.h>
#include <stdlib.h>

#define INF 25

struct Edge {
    int next_city;
    int edge_length;
    struct Edge* next;
};

struct Graph {
    struct Edge** adjacency_list;
    int* visited;
};

struct Edge* createEdge(int next_city, int edge_length) {
    struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge));
    edge->next_city = next_city;
    edge->edge_length = edge_length;
    edge->next = NULL;
    return edge;
}

void addEdge(struct Graph* graph, int curr_city, int next_city, int edge_length) {
    struct Edge* edge = createEdge(next_city, edge_length);
    edge->next = graph->adjacency_list[curr_city];
    graph->adjacency_list[curr_city] = edge;
}

int dfs(int curr, int target, struct Graph* graph) {
    if (curr == target) {
        return 0;
    }

    graph->visited[curr] = 1;
    int min_distance = INF;

    struct Edge* edge = graph->adjacency_list[curr];
    while (edge != NULL) {
        int next_city = edge->next_city;
        int edge_length = edge->edge_length;

        if (!graph->visited[next_city]) {
            int path_distance = dfs(next_city, target, graph);
            if (path_distance != INF) {
                min_distance = (edge_length + path_distance < min_distance) ? edge_length + path_distance : min_distance;
            }
        }

        edge = edge->next;
    }

    graph->visited[curr] = 0;
    return min_distance;
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
        graph->adjacency_list = (struct Edge**)malloc((n + 1) * sizeof(struct Edge*));
        graph->visited = (int*)calloc(n + 1, sizeof(int));

        for (int i = 1; i <= n; i++) {
            graph->adjacency_list[i] = NULL;
        }

        // 构建图
        while (m--) {
            int a, b, l;
            scanf("%d %d %d", &a, &b, &l);
            addEdge(graph, a, b, l);
            addEdge(graph, b, a, l);
        }

        int x, y;
        scanf("%d %d", &x, &y);

        int shortest_distance = dfs(x, y, graph);

        if (shortest_distance == INF) {
            printf("No path\n");
        } else {
            printf("%d\n", shortest_distance);
        }

        free(graph->visited);
        for (int i = 1; i <= n; i++) {
            struct Edge* edge = graph->adjacency_list[i];
            while (edge != NULL) {
                struct Edge* temp = edge;
                edge = edge->next;
                free(temp);
            }
        }
        free(graph->adjacency_list);
        free(graph);
    }
    return 0;
}