蓝桥王国--dij模板

#include <bits/stdc++.h> // 万能头
using namespace std;
typedef pair<long long ,int> PII;
int n,m;
long long  d[300011];
struct edge///邻接表
{int v;long long w;
};
int vis[300011];
vector<edge> mp[300011];///邻接表
void dij(int s)///dij单源最短
{for(int i=1;i<=n;i++)d[i]=0x3f3f3f3f3f3f3f3fLL;///无穷大d[s]=0;priority_queue<PII> pq;///优先队列pq.push({0,s});///起点startwhile(pq.size()){PII t=pq.top();pq.pop();int u=t.second;if(vis[u]) continue;///标记的跳过vis[u]=1;for(auto i:mp[u])///遍历以u起点的边{int v=i.v;long long w=i.w;if(d[v]>d[u]+w&&vis[v]==0)///更新到s的距离{d[v]=d[u]+w;pq.push({-d[v],v});///最小的点成为新点，要在最上面}}}}
int main() {cin>>n>>m;for(int i=0;i<m;i++){int u,w,v;cin>>u>>v>>w;mp[u].push_back({v,w});}dij(1);for(int i=1;i<=n;i++){if(d[i]>=0x3f3f3f3f3f3f3f3fLL){cout<<"-1 ";}else cout<<d[i]<<" ";}
} // ~ 完美结束！~

这是带符号默认从大到小的优先队列

下面是不带负号改变排序的优先队列

目录

这是带符号默认从大到小的优先队列

下面是不带负号改变排序的优先队列