单源最短路
dijkstra
时间复杂度为$\mathcal{O (n^2)}
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+8;
int n,m,s,d[N];
int cnt,head[N];
bool v[N];
struct edge{
int to,next,d;
}e[N];
void add(int x,int y,int z){
++cnt;
e[cnt].to=y;
e[cnt].d=z;
e[cnt].next=head[x];
head[x]=cnt;
}
void work(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[s]=0;
while(v[s]==0){
v[s]=1;
for(int i=head[s];i!=0;i=e[i].next){
int j=e[i].to;
if(v[j]==0&&d[j]>d[s]+e[i].d)
d[j]=min(d[j],d[s]+e[i].d);
}
int x=0x3f;
for(int i=1;i<=m;i++){
if(d[i]<x&&v[i]==0){
x=d[i];
s=i;
}
}
}
}
dijkstra+堆优化
时间复杂度为$\mathcal{O (nlog(n))}
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+8;
int n,m,s,d[N];
int cnt,head[N];
bool v[N];
struct edge{
int to,next,d;
}e[N];
void add(int x,int y,int z){
++cnt;
e[cnt].to=y;
e[cnt].d=z;
e[cnt].next=head[x];
head[x]=cnt;
}
struct code{
int d,u;
friend bool operator < (code x,code y){
return x.d>y.d;
}
};
priority_queue<code> q;
void work(){
memset(d,0x3f,sizeof(d));
d[s]=0;
q.push((code){0,s});
while(!q.empty()){
code x=q.top();q.pop();
int u=x.u;
if(v[u]==1) continue;
v[u]=1;
for(int i=head[u];i!=0;i=e[i].next){
int j=e[i].to;
if(d[j]>d[u]+e[i].d){
d[j]=d[u]+e[i].d;
q.push((code){d[j],j});
}
}
}
}
Floyd算法[双源最短路]
时间复杂度为 $\mathcal{O (n^2)}$ 的双源最短路算法。
通过枚举两点之间的中转站，来确定最短路。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
ll n,m;
ll e[N][N];
int main(){
cin>>n>>m;
memset(e,0x3f,sizeof(e));
for(int i=1;i<=n;i++) e[i][i]=0;
for(int k=1;k<=m;k++){
ll x,y,z;
cin>>x>>y>>z;
e[x][y]=min(e[x][y],z);
e[y][x]=min(e[y][x],z);
}
for(int k=1;k<=n;k++){//枚举k为中转站的时候
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<e[i][j]<<" ";
}cout<<endl;
}
return 0;
}
持续更新中.....