<>
题目描述
给定一个 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算法。
1 #include2 using namespace std; 3 4 #define INF 0x3f3f3f3f 5 const int N = 2e5+7; 6 const int M = 2e5+7; 7 int head[N],dis[N],vis[N]; 8 int n,m,s,cnt; 9 struct Edge{10 int to,val,next;11 }edge[M];12 void init(){13 cnt=0;14 memset(head,-1,sizeof(head));15 }16 void addedge(int u,int v,int w){17 edge[cnt].to=v,edge[cnt].val=w,edge[cnt].next=head[u];18 head[u]=cnt++;19 }20 struct Node{21 int index,dis;22 bool operator < (const Node & tmp)const{23 return dis>tmp.dis; //由于要保证dis小的优先,所以将dis从大到小排序 24 }25 }node[N];26 void Dij(int s){27 for(int i=1;i<=n;i++)28 vis[i]=0,node[i].index=i,node[i].dis=INF;29 priority_queue q;30 node[s].dis=0;31 q.push(node[s]);32 while(!q.empty()){33 int u = q.top().index;q.pop();34 if(vis[u])continue;35 vis[u]=1;36 for(int i=head[u];~i;i=edge[i].next){37 int v=edge[i].to;38 if(node[v].dis>node[u].dis+edge[i].val){ //更新以 u 为起点的,所有与它相连的线段的终点到s起点的最短距离39 node[v].dis = node[u].dis+edge[i].val;40 q.push(node[v]); //由于更新了d[v].dis,所以所有以d[v].index为起点的边也要更新,所以将d[v]压入队列41 }42 }43 }44 }45 int main(){46 init();47 scanf("%d%d%d",&n,&m,&s);48 for(int i=1;i<=m;i++){49 int u,v,c;scanf("%d%d%d",&u,&v,&c);50 addedge(u,v,c);51 }52 Dij(s);53 for(int i=1;i<=n;i++){54 printf("%d%s",node[i].dis,i==n?"\n":" ");55 }56 }
2018-08-13