首页 练字文章 dijkstra模板

dijkstra模板

2022-08-19 10:26  浏览数:404  来源:Coat    

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1010, inf = 0x3f3f3f3f;
int h[N],pr[N],dist[N],st[N];
int n, m,a,b,c;
char p[N];
struct node
{
int p, w;
node(int a, int b) :p(a), w(b) {};
bool operator<(const node& b) const
{
return w > b.w;
}
};
vector<node> g[N];
priority_queue<node> q;
void dijkstra()
{
memset(dist, inf, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 0;
q.push(node(1, 0));
while (q.size())
{
int temp = q.top().p;
q.pop();
if (st[temp])continue;
st[temp] = true;
for (int i = 0; i < g[temp].size(); i++)
{
int p = g[temp][i].p;
if (!st[p] && dist[temp] + g[temp][i].w < dist[p])
{
dist[p] = dist[temp] + g[temp][i].w;
q.push(node(p, dist[p]));
}
}
}
cout << dist[n]<<endl;
}
int main()
{
cin >> m>> n;
while(m--)
{
cin >> a >> b >> c;
g[a].push_back(node(b, c));
g[b].push_back(node(a, c));
}
dijkstra();
return 0;
}



声明:以上文章均为用户自行添加,仅供打字交流使用,不代表本站观点,本站不承担任何法律责任,特此声明!如果有侵犯到您的权利,请及时联系我们删除。

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)