题目链接
// 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")
}
}
}#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;
}