Dijkstra(最短路模版)
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; #define MAX 0x3f3f3f3 int mp[105][105]; //两者之间的距离 int dis[105]; //起始点到其它点的最短路程 int biaoji[105]; //标记一个点是否是旧点 int weizhi; //对到达的点进行位置标记 void Dijkstra(int m) { biaoji[1]=1; //将初始点标记 for (int i=1;i<=m;i++) //记录一开始初始点到各个点的距离 { dis[i]=mp[1][i]; } for (int i=1;i<=m;i++) { int minx=MAX; for (int j=1;j<=m;j++) { if( dis[j]<minx && biaoji[j]==0 ) //只要还有新点便进行更新 (重要) -》 我们找的新点是(所有点中 未被标记 且 距离初始点最近 的点) { minx=dis[j]; weizhi=j; } } if(minx==MAX) break; //如果距离初始点的距离都为MAX,也就是没有点可以更新,就break; biaoji[weizhi]=1; for (int j=1;j<=m;j++) //只要一个点经过标记点到初始点的距离可以更新,便更新。 { if(biaoji[j]==0 && dis[j] > (dis[weizhi])+ mp[weizhi][j]) { dis[j]=mp[weizhi][j] + dis[weizhi]; } } } } int main () { int m,n,a,b,c; while (cin >> m >> n) //m表示点数,n表示边数 { if(m==0&&n==0)break; memset(biaoji, 0, sizeof(biaoji)); //初始化 for (int i=1;i<=105;i++) //将两个点之间的距离都设为最大值 { for (int j=1;j<=105;j++) { mp[i][j]=MAX; } } for (int i=1;i<=n;i++) //遍历n条边,将两个端点之间的距离更新 { cin >> a >> b >> c; mp[a][b]=mp[b][a]=c; } Dijkstra(m); cout << dis[m] << endl; } return 0; }
堆优化 //Dijkstra的堆优化 #include <iostream> #include <queue> #include <string> #include <cstring> using namespace std; typedef long long ll; #define N 200005 #define MAX 0x3f3f3f3f3f3f3f3f ll head[N],cnt; struct sss{ ll v,w,next; }edge[N << 1]; struct node{ ll id,dis; bool operator <(const node &a) const { return dis > a.dis; //从小到大排序 } }; void add_edge(ll u,ll v,ll w){ edge[++cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt; } ll n,m,a,b,c,weizhi; ll vis[N]; //标记数组 ll dis[N]; //初始点 - 终点 的距离 void Dijkstra(){ dis[1] = 0; priority_queue<node>q; q.push(node{1,0}); while (!q.empty()) { node o = q.top(); //用优先队列直接找出距离最短的点 q.pop(); ll weizhi = o.id; if(vis[weizhi]==1) continue; vis[weizhi] = 1; for (ll i=head[weizhi] ; i!=-1 ; i=edge[i].next){ //遍历与i的每一条边 ll j = edge[i].v; if(vis[j] == 1) continue; if(dis[j] > dis[weizhi] + edge[i].w){ dis[j] = dis[weizhi] + edge[i].w; q.push(node{j,dis[j]}); } } } } void init(){ memset(vis, 0, sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=MAX; // memset(dis, MAX, sizeof(dis)); memset(head, -1, sizeof(head)); cnt = 0; for (int i=1;i<=m;i++){ cin >> a >> b >> c; add_edge(a, b, c); add_edge(b, a, c); } } int main() { cin >> n >> m; init(); Dijkstra(); if(dis[n] == MAX) cout << "qwb baka" << endl; else cout << dis[n] << endl; return 0; }
模版专项 文章被收录于专栏
模版