算法提高课-图论-单源最短路的建图方式-AcWing 1129. 热浪:dijkstra裸题

题目分析

来源：acwing

分析：

ac代码
朴素的dijkstra() ，时间复杂度$O(n^2)$

#include<bits/stdc++.h> using namespace std; const int N = 2510;bool st[N]; int g[N][N]; int n, m, S, T; int dist[N];int dijkstra(int start, int end){memset(dist, 0x3f, sizeof dist);dist[start] = 0;for(int i = 0; i< n; i ++){int t = -1;for(int j = 1; j<= n; j++)if(!st[j] &&(t == -1 || dist[j] < dist[t]))t = j;st[t] = true;for(int j = 1; j <= n;j ++)dist[j] = min(dist[j], dist[t] + g[t][j]);}return dist[end]; }int main(){memset(g, 0x3f, sizeof g);cin >> n >> m >> S >> T;while(m--){int a, b ,c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b],c);}cout <<dijkstra(S,T) << endl;}

题目来源

https://www.acwing.com/problem/content/1131/

总结

以上是生活随笔为你收集整理的算法提高课-图论-单源最短路的建图方式-AcWing 1129. 热浪:dijkstra裸题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。