P1344 最短路径问题 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年6月30日 16:49

最短路径问题（距离+花费）

P1344

回复 0 | 赞 2 | 浏览 506

经典dijkstra算法改动： 1）优先队列 q 的排序方法加上花费（钱）； 2）增加花费数组 cost，同时更新 dist 和 cost 。【本质】原比较条件：距离；现比较条件：距离、花费。 #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int maxn = 1005; struct edge { int u, v, w, c; edge(int u, int v, int w, int c): u(u),...

帅就一个字

2023年4月3日 11:03

最短路径问题-迪杰斯特拉算法

P1344

回复 0 | 赞 2 | 浏览 2.2k

首先这个题目按照题意是不能用floyd算法的，因为点的个数最大为1000，而floyd算法的复杂度为n*n*n，如果正式上机会超时。既然已经决定要用迪杰斯特拉算法，那么首先考虑存储方式，这个题目即可以邻接链表，也可以邻接矩阵。邻接矩阵法： #include<stdio.h> #define N 1001 #define MAX 110000000 int dis[N][N]; //表示距离的邻接矩阵 int cost[N][N]; //表示花费的邻接矩阵 int adis[N]; //单点到其他点的距离最小值 int acost[N]...

2023年1月15日 11:59

堆优化dijkstra

P1344

回复 0 | 赞 2 | 浏览 3.8k

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=300086; typedef pair<int, int> PII; int n,m,s,t2; // 点的数量 int h[N], w[N], e[N], ne[N], idx,cost[N]; // 邻接表存储所有边 int cnt[N]; int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个...

2021年1月26日 11:57

签到

P1344

回复 0 | 赞 0 | 浏览 9.1k

#include<iostream> #include<string> #include<string.h> #include<vector> #include<stdio.h> #include <queue> #include<algorithm> using namespace std; const int maxn=1005; struct Edge { int u; int v; int dis; int cos; Edge(int a,int b...

题目最短路径问题

题解数量4

热门题解

1 堆优化dijkstra

2 最短路径问题-迪杰斯特拉算法

3 最短路径问题（距离+花费）

4 签到