堆优化版：通过定义一个最小堆来实现普通版本中的查找操作
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 100005
const double PI = 3.14159265358979323846;
using namespace std;
int n, m, s;
int dis[N];
bool vis[N];
struct Node{
int v, w;
bool operator > (const Node& other)const//重载
{
return w > other.w;
}
};
vector<Node>vec[N];
void dijkstra()
{
fill(dis, dis + n + 1, INF);
fill(vis, vis, false);
dis[s] = 0;
priority_queue<Node, vector<Node>, greater<Node>>q;//小根堆
q.push({ s,0 });
while (!q.empty())
{
Node cur = q.top(); q.pop();
if (vis[cur.v])continue;
vis[cur.v] = true;
for (auto ve : vec[cur.v])
{
if (dis[ve.v] > dis[cur.v] + ve.w)
{
dis[ve.v] = dis[cur.v] + ve.w;
q.push({ ve.v,dis[ve.v] });
}
}
}
}
signed main()
{
ios;//会超时
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int u, v, w; cin >> u >> v >> w;
vec[u].push_back({ v,w });
}
dijkstra();
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
return 0;
}