（4）单源最短路径

题目描述

给定一个N个点，M 条有向边的带非负权图，请你计算从S出发，到每个点的距离。 数据保证你能从 S 出发到任意点。（1≤N≤100000，1≤M≤200000，S=1 ）

算法：dijkstra+堆优化+链式前向星

 

struct edge { int to,w,nxt; } e[M]; struct node { int id,dis; friend bool operator<(const node& a,const node& b) { return a.dis>b.dis; } }; int head[M],dis[M],c,s; void add(int x,int y,int w) { e[++c].to=y; e[c].w=w; e[c].nxt=head[x]; head[x]=c; } priority_queue<node>q; void dijkstra() { memset(dis,0x3f,sizeof dis); dis[s]=0; q.push((node){s,0}); while(!q.empty()) { node t=q.top(); q.pop(); if(dis[t.id]!=t.dis) continue; for(int i=head[t.id]; i; i=e[i].nxt) { int to=e[i].to,w=e[i].w; if(dis[t.id]+w<dis[to]) { dis[to]=dis[t.id]+w; q.push((node){to,dis[to]}); } } } } int main() { int n,m,x,y,z; cin>>n>>m>>s; for(int i=1; i<=m; i++) { qcin(x),qcin(y),qcin(z); add(x,y,z); } dijkstra(); for(int i=1; i<=n; i++) cout<<dis[i]<<' '; }