本文主要是介绍2673 最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
朴素Dijkstra算法
包含重边和自环
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
int G[N][N];
int n, m;
int d[N];
bool st[N];
void Dijkstra(int s){memset(d, 0x3f, sizeof d);d[s] = 0;for(int i = 0; i < n; i++){ //迭代n次 int u = -1;for(int j = 1; j <= n; j++)if(!st[j] && (u == -1 || d[u] > d[j])){u = j;}st[u] = true;for(int v = 1; v <= n; v++){d[v] = min(d[v], d[u] + G[u][v]);}}
}
int main(){cin>>n>>m;int u, v, w;memset(G, 0x3f,sizeof G);for(int i = 0; i < m; i++){cin>>u>>v>>w;G[u][v] = min(w, G[u][v]);G[v][u] = min(w, G[v][u]);}int st, ed;cin>>st>>ed;Dijkstra(st);cout<<d[ed]<<endl;return 0;
}
这篇关于2673 最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
