Dijkstra
- 初始版本：
1.思路分析：用vis数组记录每个点是否被访问过。从原点开始拓展n-1次，计算到每个点的最小距离。每次循环寻找一个距离原点最近的点，然后做松弛操作，更新那些距离更远点。时间复杂度O(n^2)。
- 算法板子：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
struct ty {
int v,w;
};
vector<ty> g[N];
int dis[N],vis[N];
int n,m;
void dijkstra() {
for(int i = 0 ; i <= n; i++) dis[i] = inf;
dis[1] = 0;
for(int i = 1; i <= n - 1; i++) {
int pos = 0;
for(int j = 1; j <= n; j++) {
if(dis[j] < dis[pos] && !vis[j]) pos = j;
}
vis[pos] = 1;
for(auto i : g[pos]) {
if(dis[i.v] > dis[pos] + i.w) {
dis[i.v] = dis[pos] + i.w;
}
}
}
}
void solved() {
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
}
dijkstra();
if(dis[n] == inf) {
cout << -1 << "\n";
} else cout << dis[n] << "\n";
}
int main() {
int t = 1;
//cin >> t;
while(t--) {
solved();
}
return 0;
}
- 堆优化版本
- 思路分析：内部循环我只需要找到边最近的然后进行更行就可以了，所以可以把点放到堆里面。每次就不用循环n次了。内部循环中的堆查找堆顶的复杂度就是logm(m是边的数量)，因为所有的边都要走一遍，所以算法复杂度是mlogm；
- 算法板子：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
struct ty {
int v,w;
};
vector<ty> g[N];
int dis[N],vis[N];
int n,m;
void dijkstra() {
priority_queue<PII,vector<PII>,greater<PII>> q;
for(int i = 0 ; i <= n; i++) dis[i] = inf;
//cout << dis[2] << "\n";
dis[1] = 0;
q.push({0,1});
while(!q.empty()) {
auto t = q.top();q.pop();
if(vis[t.second]) continue;
vis[t.second] = 1;
for(auto i : g[t.second]) {
if(dis[i.v] > dis[t.second] + i.w) {
dis[i.v] = dis[t.second] + i.w;
q.push({dis[i.v],i.v});
}
}
}
}
void solved() {
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
}
dijkstra();
if(dis[n] == inf) {
cout << -1 << "\n";
} else cout << dis[n] << "\n";
}
int main() {
int t = 1;
//cin >> t;
while(t--) {
solved();
}
return 0;
}