7-5 单源最短路径
请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。
输入样例:
4 4
0 1 1
0 3 1
1 3 1
2 0 1
输出样例:
1 1
简化版代码
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
vector<pair<int, int>> mp[N];
bool vis[N];
int dis[N];
int main()
{
memset(dis, INF, sizeof dis);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m ;++i) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
mp[u].push_back({v, w});
}
priority_queue<PII, vector<PII>, greater<PII>> q;
dis[0] = 0;
q.push({0, 0});
while (q.size()) {
auto [d, u] = q.top();
q.pop();
if (vis[u]) continue;
dis[u] = d;
vis[u] = true;
for (auto [v, w] : mp[u]) {
if (dis[v] < dis[u] + w) continue;
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
for (int i = 1; i < n; ++i) {
if (dis[i] == INF) continue;
printf("%d ", dis[i]);
}
return 0;
}
中文注释版代码
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
vector<pair<int, int>> mp[N]; // 邻接表存储图的边权信息
bool vis[N]; // 记录节点是否已经被访问
int dis[N]; // 记录源点到各个节点的最短距离
int main()
{
memset(dis, INF, sizeof dis); // 初始化距离数组为无穷大
int n, m;
scanf("%d %d", &n, &m);
// 输入边的信息并构建邻接表
for (int i = 0; i < m ;++i) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
mp[u].push_back({v, w});
}
priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆存储节点距离信息
dis[0] = 0; // 源点到自身的距离为0
q.push({0, 0}); // 将源点加入堆中
while (q.size()) {
auto [d, u] = q.top();
q.pop();
if (vis[u]) continue; // 如果节点已经被访问过，则跳过
dis[u] = d; // 更新最短距离
vis[u] = true; // 标记节点已经被访问
// 遍历与当前节点相邻的节点
for (auto [v, w] : mp[u]) {
if (dis[v] < dis[u] + w) continue; // 如果新的路径没有更短，则跳过
dis[v] = dis[u] + w; // 更新最短距离
q.push({dis[v], v}); // 将新的节点加入堆中
}
}
// 输出从源点到各个节点的最短距离
for (int i = 1; i < n; ++i) {
if (dis[i] <span style="font-weight: bold;" class="mark"> INF) continue; // 如果无法到达该节点，则跳过
printf("%d ", dis[i]);
}
return 0;
}
java版代码（有问题）
注意：运行超时，如果有谁的java代码过了，可以给发在评论区或私信我==
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class Pair implements Comparable<Pair> {
Integer key;
Integer value;
public Pair(Integer key, Integer value) {
this.key = key;
this.value = value;
}
@Override
public int compareTo(Pair o) {
return this.value - o.value;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] dis = new int[n]; // 记录源点到各个节点的最短距离
Arrays.fill(dis, Integer.MAX_VALUE); // 初始化距离数组为无穷大
boolean[] vis = new boolean[n]; // 记录节点是否已经被访问
ArrayList<Pair>[] mp = new ArrayList[n]; // 邻接表存储图的边权信息
for (int i = 0; i < n; ++i) {
mp[i] = new ArrayList<>();
}
// 输入边的信息并构建邻接表
for (int i = 0; i < m; ++i) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
mp[u].add(new Pair(v, w));
}
PriorityQueue<Pair> q = new PriorityQueue<>(); // 小顶堆存储节点距离信息
dis[0] = 0; // 源点到自身的距离为0
q.add(new Pair(0, 0)); // 将源点加入堆中
while (!q.isEmpty()) {
Pair pair = q.poll();
int d = pair.key;
int u = pair.value;
if (vis[u]) continue; // 如果节点已经被访问过，则跳过
dis[u] = d; // 更新最短距离
vis[u] = true; // 标记节点已经被访问
// 遍历与当前节点相邻的节点
for (Pair edge : mp[u]) {
int v = edge.key;
int w = edge.value;
if (dis[v] < dis[u] + w) continue; // 如果新的路径没有更短，则跳过
dis[v] = dis[u] + w; // 更新最短距离
q.add(new Pair(dis[v], v)); // 将新的节点加入堆中
}
}
// 输出从源点到各个节点的最短距离
for (int i = 1; i < n; ++i) {
if (dis[i] == Integer.MAX_VALUE) continue; // 如果无法到达该节点，则跳过
System.out.print(dis[i] + " ");
}
}
}