<题目链接>
题目描述
给定一个 N 个点, M 条有向边的带非负权图,请你计算从 S 出发,到每个点的距离。
数据保证你能从 S 出发到任意点。
输入格式:
第一行为三个正整数 N,M,S 。 第二行起 M 行,每行三个非负整数 ui, vi, wi,表示从 ui到 vi 有一条权值为 wi 的边。
输出格式:
输出一行 N 个空格分隔的非负整数,表示 S 到每个点的距离。
1<=N<=100000
1<=M<=200000
解题分析:
由于n和m的数据太大,所以这里不能够用普通的dijkstra算法,因为它的复杂度为$O(n^2)$,所以我们这里要用的是复杂度为$O(mlog(n))$的加上堆优化的dijkstra算法。
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f ; ; int head[N],dis[N],vis[N]; int n,m,s,cnt; struct Edge{ int to,val,next; }edge[M]; void init(){ cnt=; memset(head,-,sizeof(head)); } void addedge(int u,int v,int w){ edge[cnt].to=v,edge[cnt].val=w,edge[cnt].next=head[u]; head[u]=cnt++; } struct Node{ int index,dis; bool operator < (const Node & tmp)const{ return dis>tmp.dis; //由于要保证dis小的优先,所以将dis从大到小排序 } }node[N]; void Dij(int s){ ;i<=n;i++) vis[i]=,node[i].index=i,node[i].dis=INF; priority_queue<Node>q; node[s].dis=; q.push(node[s]); while(!q.empty()){ int u = q.top().index;q.pop(); if(vis[u])continue; vis[u]=; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].to; if(node[v].dis>node[u].dis+edge[i].val){ //更新以 u 为起点的,所有与它相连的线段的终点到s起点的最短距离 node[v].dis = node[u].dis+edge[i].val; q.push(node[v]); //由于更新了d[v].dis,所以所有以d[v].index为起点的边也要更新,所以将d[v]压入队列 } } } } int main(){ init(); scanf("%d%d%d",&n,&m,&s); ;i<=m;i++){ int u,v,c;scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); } Dij(s); ;i<=n;i++){ printf("%d%s",node[i].dis,i==n?"\n":" "); } }
2018-08-13