题目链接：https://www.luogu.com.cn/problem/P4779
题目描述：给定一个 n 个点，m 条有向边的带非负权图，计算从 s 出发，到每个点的距离。
这道题就是一个单源最短路径的模板，有两种做法：
1.Floyd算法
暴力枚举出所有起点、终点以及中间值，然后算出每两个点间的最小值。
但这个算法时间复杂度较高，是O（n^3），很容易爆掉，在这道题甚至拿不到分。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int arr[10000][10000]; 4 int main(){ 5 int n,m,s,i,j,k,a,b,c; 6 cin>>n>>m>>s; 7 for(i=1;i<=n;i++){ 8 for(j=1;j<=n;j++){ 9 if(i==j){10 arr[i][j]=0;11 }else{12 arr[i][j]=99999999;13 }14 }15 }16 while(m--){17 cin>>a>>b>>c;18 arr[a][b]=min(c,arr[a][b]);19 }20 for(k=1;k<=n;k++){21 for(i=1;i<=n;i++){22 if(i==k||arr[i][k]==99999999){23 continue;24 }25 for(j=1;j<=n;j++){26 arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);27 } 28 }29 }30 for(i=1;i<=n;i++){31 cout<<arr[s][i]<<" "; 32 }33 }
这道题我们要用一种更高级的算法——
2.dijkstra算法
在无负权边的情况下，时间复杂度为 O（n log n）基本可以顺利通过所有模板题。
先确定初始点到其他所有点的路径（可能为无穷），然后从和该点距离最小点开始遍历，不断更新这些点与初始点的最小距离（学术名叫松弛），最后求出初始点与所有其他点的最短路。
然后要通过此题，还需要前向星存边和优先队列（堆）优化，可能比较难理解，自己画图模拟即可。
上代码（有注释）：
1 #include<bits/stdc++.h> 2 using namespace std; 3 long long vis[100001]={0},head[100001],dis[100001],cnt,n,m,s,a,b,c; 4 long long INF=2147483647;//2的31次方，可以看做无穷 5 struct Q{ 6 int a,b,c,next; 7 };//邻接表，在有向图中存储起点、终点权值，next用来前向星存边 8 struct node{//放进优先队列中的结构体 9 int w,now;//w为最短路，now为点 10 bool operator <(const node &x)const{11 return w>x.w;//权值从大到小排 12 }13 };14 priority_queue<node> q;//优先队列 15 Q e[500001];16 void add(int a,int b,int c){//前向星存边 17 e[cnt++].a=a;18 e[cnt].b=b;19 e[cnt].c=c;20 e[cnt].next=head[a];//next存储上一个cnt值，方便for循环从后往前遍历边 21 head[a]=cnt;22 } 23 void dijkstra(){24 for(int i=1;i<=n;i++){25 dis[i]=INF;26 }27 dis[s]=0;28 q.push((node){0,s});//将起点压入队列 29 while(!q.empty()){//队列非空 30 node x=q.top();//弹出堆顶（最小）元素 31 q.pop();32 int u=x.now;33 if(vis[u]==1){34 continue;//遍历完无需再遍历 35 }36 vis[u]=1;37 for(int i=head[u];i;i=e[i].next){//用前向星遍历 38 int v=e[i].b; 39 dis[v]=min(dis[v],dis[u]+e[i].c);//松弛操作 40 q.push((node){dis[v],v});41 }42 }43 }44 int main(){45 cin>>n>>m>>s;46 for(int i=0;i<m;i++){47 cin>>a>>b>>c;48 add(a,b,c);49 }50 dijkstra(); 51 for(int i=1;i<=n;i++){52 cout<<dis[i]<<" ";53 }54 }
