企业门户网站建设教程,WordPress电影公司网站主题,专业的公司网站设计服务,网站开发后台技术7-5 单源最短路径
请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点#xff0c;编号为0至n-1#xff0c;以顶点0作为源点。
输入格式:
输入第一行为两个正整数n和e#xff0c;分别表示图的顶点数和边数#xff0c;其中n不超过20000#xff0c;e不超过10…7-5 单源最短路径
请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点编号为0至n-1以顶点0作为源点。
输入格式:
输入第一行为两个正整数n和e分别表示图的顶点数和边数其中n不超过20000e不超过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 pairint, int;const int INF 0x3f3f3f3f;
const int N 2e4 10;vectorpairint, 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_queuePII, vectorPII, greaterPII 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 pairint, int;const int INF 0x3f3f3f3f;
const int N 2e4 10;vectorpairint, 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_queuePII, vectorPII, greaterPII q; // 小顶堆存储节点距离信息dis[0] 0; // 源点到自身的距离为0q.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 stylefont-weight: bold; classmark 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 ComparablePair {Integer key;Integer value;public Pair(Integer key, Integer value) {this.key key;this.value value;}Overridepublic 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]; // 记录节点是否已经被访问ArrayListPair[] 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));}PriorityQueuePair q new PriorityQueue(); // 小顶堆存储节点距离信息dis[0] 0; // 源点到自身的距离为0q.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] );}}
}
