一、Dijkstra算法模板:
#include <bits/stdc++.h> using namespace std; const int N=10010,M=100010; int head[N],edge[M],ver[M],Next[M],d[N]; bool v[N]; int n,m,tot; priority_queue< pair<int,int> >q;//pair的第一维为dist的相反数,第二维为节点编号 //大根堆(优先队列),使用相反数变成小根堆。 void add(int x,int y,int z){ ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot; } void dijkstra(){ memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; q.push(make_pair(0,1)); while(q.size()){ int x=q.top().second; q.pop(); if(v[x]) continue; v[x]=1; for(int i=head[x];i;i=Next[i]){ int y=ver[i],z=edge[i]; if(d[y]>d[x]+z){ d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; add(x,y,z); } dijkstra(); for(int i=1;i<=n;i++) cout<<d[i]<<" "; return 0; }