thinkphp5 网站开发,湖南网站建设费用,官方网站建设有限公司,wordpress 建站教程P3371 P4779
P3371 【模板】单源最短路径#xff08;弱化版#xff09;
注意的点#xff1a;
边有重复#xff0c;选择最小边#xff01;对于SPFA算法容易出现重大BUG#xff0c;没有负权值的边时不要使用#xff01;#xff01;#xff01;
70分代码 朴素板dijsk…P3371 P4779
P3371 【模板】单源最短路径弱化版
注意的点
边有重复选择最小边对于SPFA算法容易出现重大BUG没有负权值的边时不要使用
70分代码 朴素板dijsktra
爆空间
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, s, u, v, w;
void solve() {cin n m s;vectorvectorintgrid(n 9, vectorint(n 9, INT_MAX));vectorintdist(n 9, INT_MAX);vectorboolvisited(n 9, false);while (m--) {cin u v w;grid[u][v] min(grid[u][v], w);}dist[s] 0;for (int i 1; i n; i) {int cur 1;int minDist INT_MAX;for (int j 1; j n; j) {if (!visited[j] dist[j] minDist) {minDist dist[j];cur j;}}visited[cur] true;for (int j 1; j n; j) {if (!visited[j] grid[cur][j] ! INT_MAX dist[cur] grid[cur][j] dist[j]) {dist[j] dist[cur] grid[cur][j];}}/*cout select cur endl;for (int i 1; i n; i) {cout dist[i] ;}cout endl;*/}for (int i 1; i n; i) {cout dist[i] ;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}32分代码 SPFA
因为有重复指向的边所有理论上边数可以无穷大O(KM)的时间复杂度不确定性极大
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, s, u, v, w;
struct Edge {int v, w;Edge(int a, int b) :v(a), w(b) {}
};
void solve() {cin n m s;vectorlistEdgegrid(n 9, listEdge());vectorintdist(n 9, INT_MAX); dist[s] 0;queueEdgeq;while (m--) {cin u v w;grid[u].push_back(Edge(v, w));}q.push({ s,0 });while (!q.empty()) {Edge cur q.front();q.pop();for (auto item : grid[cur.v]) {if (item.w dist[cur.v] dist[item.v]) {dist[item.v] dist[cur.v] item.w;q.push(item);}}}for (int i 1; i n; i) {cout dist[i] ;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}AC代码 堆优化dijsktra
重复的边不影响
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, s, u, v, w;
struct Edge {int v, w;Edge(int a, int b) :v(a), w(b) {}
};
class cmp {
public:bool operator()(const Edge a, const Edge b) {return a.w b.w;//从小排序}
};void solve() {cin n m s;vectorlistEdgegrid(n 9, listEdge());vectorintdist(n 9, INT_MAX); dist[s] 0;vectorboolvisited(n 9, false);priority_queueEdge, vectorEdge, cmpq;while (m--) {cin u v w;grid[u].push_back(Edge(v, w));}q.push({ s,0 });while (!q.empty()) {Edge cur q.top();q.pop();if (visited[cur.v]) {continue;}visited[cur.v] true;for (auto item : grid[cur.v]) {if (!visited[item.v]item.w dist[cur.v] dist[item.v]) {dist[item.v] item.w dist[cur.v];q.push({ item.v,dist[item.v] });}}}for (int i 1; i n; i) {cout dist[i] ;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}P1144
最短路计数
题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始到其他每个点的最短路有几条。
输入格式
第一行包含 2 2 2 个正整数 N , M N,M N,M为图的顶点数与边数。
接下来 M M M 行每行 2 2 2 个正整数 x , y x,y x,y表示有一条连接顶点 x x x 和顶点 y y y 的边请注意可能有自环与重边。
输出格式
共 N N N 行每行一个非负整数第 i i i 行输出从顶点 1 1 1 到顶点 i i i 有多少条不同的最短路由于答案有可能会很大你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 i i i 则输出 0 0 0。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 6 1\le N\le10^6 1≤N≤106 1 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^6 1≤M≤2×106。
AC题解 堆优化dijsktra
多一段条件判断不加入堆但是也起到了统计作用
else if (dist[cur.v] item.w dist[item.v]) {ct[item.v] ct[cur.v];ct[item.v] % 100003;}#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, x, y;
struct Edge {int v, w;Edge(int a, int b) :v(a), w(b) {};
};
class cmp {
public:bool operator()(const Edge a, const Edge b) {return a.w b.w;}
};
priority_queueEdge,vectorEdge,cmpq;
void solve() {cin n m;vectorlistEdgegrid(n 9, listEdge());vectorboolvisited(n 9, false);vectorintdist(n9, INT_MAX);vectorintct(n9, 0);while (m--) {cin x y;grid[x].push_back(Edge(y, 1));grid[y].push_back(Edge(x, 1));}dist[1] 0; ct[1] 1;q.push({ 1,0 });while (!q.empty()) {Edge curq.top();q.pop();if (visited[cur.v]) {continue;}visited[cur.v] true;for (auto item : grid[cur.v]) {if (dist[cur.v] item.w dist[item.v]) {dist[item.v] dist[cur.v] item.w;ct[item.v] ct[cur.v];q.push({ item.v,dist[item.v] });}else if (dist[cur.v] item.w dist[item.v]) {ct[item.v] ct[cur.v];ct[item.v] % 100003;}}}//for (int i 1; i n; i) {// cout dist[i] ;//}for (int i 1; i n; i) {cout ct[i] endl;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}P5905
【模板】全源最短路Johnson
题目描述
给定一个包含 n n n 个结点和 m m m 条带权边的有向图求所有点对间的最短路径长度一条路径的长度定义为这条路径上所有边的权值和。
注意 边权可能为负且图中可能存在重边和自环 部分数据卡 n n n 轮 SPFA 算法。
输入格式
第 1 1 1 行 2 2 2 个整数 n , m n,m n,m表示给定有向图的结点数量和有向边数量。
接下来 m m m 行每行 3 3 3 个整数 u , v , w u,v,w u,v,w表示有一条权值为 w w w 的有向边从编号为 u u u 的结点连向编号为 v v v 的结点。
输出格式
若图中存在负环输出仅一行 − 1 -1 −1。
若图中不存在负环
输出 n n n 行令 d i s i , j dis_{i,j} disi,j 为从 i i i 到 j j j 的最短路在第 i i i 行输出 ∑ j 1 n j × d i s i , j \sum\limits_{j1}^n j\times dis_{i,j} j1∑nj×disi,j注意这个结果可能超过 int 存储范围。
如果不存在从 i i i 到 j j j 的路径则 d i s i , j 1 0 9 dis_{i,j}10^9 disi,j109如果 i j ij ij则 d i s i , j 0 dis_{i,j}0 disi,j0。
右图为样例 2 2 2 给出的有向图红色标注的边构成了负环注意给出的图不一定连通。 Johnson算法
数据溢出longlong的转换h[item.v] h[cur.v] item.w;这段代码是Johnson算法的精髓势能函数dist[j] h[j] - h[st]由于路径上每一个边i,j都加入了h[i]-h[j],所以最短距离应该要 末位 - 首位才是最终距离
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m;
ll u,v,w;
void dijsktra(int st,vectorlldist);
struct Edge {ll v, w;Edge(ll a, ll b) :v(a), w(b) {};
};
class cmp {
public:bool operator()(const Edge a, const Edge b) {return a.w b.w;}
};
ll inf ll(1e9);
queueEdgeq;
vectorintct(3009, 0);
vectorlistEdgeedges(3009, listEdge());
vectorllh(3009, inf);vectorlldist(3009, inf);
priority_queueEdge, vectorEdge, cmps;
bool visited[3009];
void solve() {cin n m;while(m--) {cin u v w;edges[u].push_back({ v,w });}for (int i 1; i n; i) {edges[0].push_back({ i,0 });}h[0] 0;q.push({ 0,0 }); ct[0] 1;while (!q.empty()) {Edge cur q.front();q.pop();if (ct[cur.v] n) {cout -1;return;}for (auto item : edges[cur.v]) {if (h[cur.v] item.w h[item.v]) {h[item.v] h[cur.v] item.w;ct[item.v] ;q.push(item); }}}/* cout h endl;for (int i 0; i n; i) {cout h[i] ;}cout endl;*//*重组edges数组*/for (int i 1; i n; i) {for (auto item : edges[i]) {item.w item.wh[i] - h[item.v];}}for (int i 1; i n; i) {dijsktra(i,dist);}
}
void dijsktra(int st,vectorlldist) {memset(visited, false, sizeof(visited));dist[st] 0; s.push({ st,0 });while (!s.empty()) {Edge cur s.top();s.pop();if (visited[cur.v]) {continue;}visited[cur.v] true;for (auto item : edges[cur.v]) {if (!visited[item.v]dist[cur.v] item.w dist[item.v]) {dist[item.v] item.w dist[cur.v];s.push({ item.v,dist[item.v] });}}}/*for (int i 1; i n; i) {cout dist[i] ;}cout endl;*/ll ans 0;for (int j 1; j n; j) {if (dist[j] inf) {ans ll(j) * dist[j];}else {ans ll(j) * (dist[j] h[j] - h[st]);}}cout ans endl;
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}今日总结
dijsktra不能用于负权值Bellman可以用于检测负权回路SFPA算法不要轻易用容易爆死Floyd 算法时间复杂度O(n3),dijsktra O(mlogm),Johnson算法时间复杂度接近 O(nmlogn)相当于用SFPA扫除了dijsktra不能求负权值边的障碍最终还是要归结于dijsktra算法堆优化版来说人话就是Bellman和SFPA太慢dijsktra用不了所以采用Johnson算法
