|
发表于 2020-1-11 23:19:34
|
显示全部楼层
- /*
- 由于本人没学Floyd就介绍 Dijkstra和SPFA
- 代码为c++
- 第一段代码用的是spfa算法,相对来说时间复杂度更高一些
- 如果图随机生成,时间复杂度为O(KM) (常数k想小一点小就看你自己怎么优化了)
- 但是实际上SPFA的算法复杂度是O(NM)。
- 不怎么推荐这个算法,比如2018年NOi比赛就卡了SPFA时间复杂度
- (K可以当作常数,m边数,n点数)
- */
- #include <iostream>
- #include <cstdio>
- #include <queue>
- #define MAXN 10010
- #define MAXM 500010
- #define INF 2147483647
- using namespace std;
- queue<int> q;
- struct Edge {
- int next,to,w;
- }edge[MAXM];
- int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];
- void spfa() {
- for(int i=1;i<=n;i++)
- dis[i] = INF;
- q.push(s);
- dis[s] = 0;
- vis[s] = 1;
- while(!q.empty()) {
- int u = q.front();
- q.pop();
- vis[u] = 0;
- for(int i=head[u];i;i=edge[i].next) {
- int v = edge[i].to;
- if(dis[v]>dis[u]+edge[i].w) {
- dis[v] = dis[u] + edge[i].w;
- if(!vis[v]) {
- vis[v] = 1;
- q.push(v);
- }
- }
- }
- }
- }
- void edge_add(int u,int v,int w) {
- cnt++;
- edge[cnt].next = head[u];
- edge[cnt].to = v;
- edge[cnt].w = w;
- head[u] = cnt;
- }
- int main() {
- cin >> n >> m >> s;
- for (int i=1;i<=m;i++) {
- int u,v,w;
- cin >> u >> v >> w;
- edge_add(u,v,w);
- }
- spfa();
- for(int i=1;i<=n;i++)
- cout << dis[i] << " ";
- return 0;
- }
- /*下面这段代码是Dijkstra
- 采用了优先队列priority_queue+重载的堆优化
- priority_queue是c++ stl库里的东西,可以学习下
- 时间按复杂度O( (n+m) log n)
- m很大的时候会比较慢
- 不过总的来说比SPFA优化了许多
- */
- #include <iostream>
- #include <cstdio>
- #include <queue>
- #define MAXN 100100
- #define MAXM 5000100
- #define INF 2147483647
- using namespace std;
- struct Edge {
- int next,to,w;
- }edge[MAXM];
- int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];
- struct node {
- int pos,dis;
- bool operator<(const node &a) const{
- return a.dis<dis;
- }
- };
- priority_queue<node> q;
- void dj() {
- for(int i=1;i<=n;i++)
- dis[i] = INF;
- dis[s] = 0;
- node tmp;
- tmp.pos = s;
- tmp.dis = 0;
- q.push(tmp);
- while(!q.empty()) {
- int u = q.top().pos;
- q.pop();
- if(!vis[u]) {
- vis[u] = 1;
- for(int i=head[u];i;i=edge[i].next) {
- int v = edge[i].to;
- if(dis[v]>dis[u]+edge[i].w) {
- dis[v] = dis[u] + edge[i].w;
- tmp.pos = v;
- tmp.dis = dis[v];
- q.push(tmp);
- }
- }
- }
- }
- }
- void edge_add(int u,int v,int w) {
- cnt++;
- edge[cnt].next = head[u];
- edge[cnt].to = v;
- edge[cnt].w = w;
- head[u] = cnt;
- }
- int main() {
- cin >> n >> m >> s;
- for (int i=1;i<=m;i++) {
- int u,v,w;
- cin >> u >> v >> w;
- edge_add(u,v,w);
- }
- dj();
- for(int i=1;i<=n;i++)
- cout << dis[i] << " ";
- return 0;
- }
复制代码 |
|