[kuangbin带你飞]专题四最短路练习

2022/9/15 0:23:43

Til the Cows Come HomePOJ - 2387

题意：给你一幅地图，点1~N，双向正权路，问你N到1的最短路径？

算法：Dijkstra或者SPFA

思路：因为是正权路径，可以用Dijkstra算法；SPFA区别就是可以判断负权环。

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <cstdio>
 7 #include <map>
 8 #include <math.h>
 9 
10 using namespace std;
11 
12 const int INF = 0x3f3f3f3f;
13 const int MAXN = 1000+10;
14 
15 struct qnode{
16     int v,c;
17     qnode(int _v=0,int _c=0):v(_v),c(_c) {}
18     bool operator < (const qnode &r)const{
19         return c>r.c;
20     }
21 };
22 struct Edge{
23     int v,cost;
24     Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
25 };
26 vector<Edge>E[MAXN];
27 void addedge(int u,int v,int w){E[u].push_back(Edge(v,w));}
28 bool vis[MAXN];
29 int dist[MAXN];
30 void Dijkstra(int n,int start){
31     memset(vis,false,sizeof vis);
32     for(int i=1;i<=n;i++) dist[i]=INF;
33     priority_queue<qnode> q;
34     dist[start]=0;
35     q.push(qnode(start,0));
36     while(!q.empty()){
37         qnode tmp = q.top();q.pop();
38         int u = tmp.v;
39         if(vis[u]) continue;
40         vis[u]=true;
41         for(int i=0;i<E[u].size();i++){
42             int v = E[u][i].v , cost = E[u][i].cost;
43             if(!vis[v]&&dist[v]>dist[u]+cost){
44                 dist[v] = dist[u] + cost;
45                 q.push(qnode(v,dist[v]));
46             }
47         }
48     }
49 }
50 int main()
51 {
52     int T,N;
53     cin>>T>>N;
54     while(T--){
55         int a,b,c;cin>>a>>b>>c;
56         addedge(a,b,c) , addedge(b,a,c);
57     }
58     Dijkstra(N,1);
59     cout<<dist[N]<<endl;
60     return 0;
61 }

Dijkstra

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <cstdio>
 7 #include <map>
 8 #include <math.h>
 9 
10 using namespace std;
11 
12 const int INF = 0x3f3f3f3f;
13 const int MAXN = 1000+10;
14 
15 struct Edge{
16     int v,cost;
17     Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
18 };
19 vector<Edge> E[MAXN];
20 void addedge(int u,int v,int w){E[u].push_back(Edge(v,w));}
21 bool vis[MAXN];
22 int cnt[MAXN],dis[MAXN];
23 bool SPFA(int start,int n){
24     memset(vis,false,sizeof vis);
25     for(int i=1;i<=n;i++) dis[i] = INF;
26     vis[start]=true,dis[start]=0;
27     queue<int> q;q.push(start);
28     memset(cnt,0,sizeof cnt);cnt[start] = 1;
29     while(q.size()){
30         int u = q.front();q.pop();
31         vis[u]=false;
32         for(int i=0;i<E[u].size();i++){
33             int v = E[u][i].v;
34             if(dis[v]>dis[u]+E[u][i].cost){
35                 dis[v]=dis[u]+E[u][i].cost;
36                 if(!vis[v]){
37                     vis[v] = true;
38                     q.push(v);
39                     if(++cnt[v]>n) return false;
40                 }
41             }
42         }
43     }
44     return true;
45 }
46 int main()
47 {
48     int T,N;
49     cin>>T>>N;
50     while(T--){
51         int a,b,c;cin>>a>>b>>c;
52         addedge(a,b,c) , addedge(b,a,c);
53     }
54     SPFA(1,N);
55     cout<<dis[N]<<endl;
56     return 0;
57 }

SPFA

实验一：SDN 拓扑实践

lock处理

[kuangbin带你飞]专题四 最短路练习

Til the Cows Come HomePOJ - 2387

[kuangbin带你飞]专题四最短路练习