P3371 【模板】单源最短路径（弱化版）
本题是比较经典的最短路径，同时有需要堆优化和链式前向星
dijkstra复杂度在nlogn
有关链式前向星的内容在 ：深度理解链式前向星
堆优化的内容用优先队列来实现
#include<bits/stdc++.h> using namespace std; const int maxn = 100000; const int INF = 2147483647; struct edge{ int u,v,w, next; }e[maxn]; int head[maxn]; int dis[maxn],vis[maxn]; int start,n,m,cnt = 0 ; struct node{ int w,to; inline bool operator <(const node &x)const { return w>x.w; } }; priority_queue<node>q; void add(int u,int v,int w) { e[cnt++].u= u ; e[cnt].v = v; e[cnt].w = w ; e[cnt].next = head[u]; head[u]=cnt; } //链式前向星 void dijkstra() { for(int i=0;i<=n;i++) dis[i]=INF; dis[start]=0; q.push(node {0,start}); while(!q.empty()) { node x = q.top();q.pop(); int u = x.to; if(vis[u])continue; vis[u]=1; for(int i =head[u];i;i=e[i].next) { int v = e[i].v; if(dis[v]>dis[u]+e[i].w) { dis[v] = dis[u] + e[i].w; q.push(node{dis[v],v}); } } } } int main(){ int u,v,w; scanf("%d%d%d",&n,&m,&start); for(int i= 1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w);//Oneway } dijkstra(); for(int i=1;i<=n;i++) printf("%d ",dis[i]); return 0; }
