其实这篇文章曾经在初赛复习里，只是觉得把它拿出来以后可能找的更方便一些。
- Dijkstra:贪心策略，每次取与源点距离最近的点。一个点不能重复入堆，不适用于负权边（或负环）
- 朴素版
#include<bits/stdc++.h>
using namespace std;
#define inf 1e8
int mark[10005],dis[10005];
struct node{int to,v;};
vector<node>edge[10005];
int main(){
int n,m,s,t,x,y,z;
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(dis,0,sizeof(dis));dis[s]=0;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
edge[x].push_back(node<%y,z%>);
}
for(int j=1;j<=n;j++){
int len=inf*2,p;
for(int i=1;i<=n;i++)
if(!mark[i]&&dis[i]<len)len=dis[i],p=i;
mark[p]=1;
for(int i=0;i<edge[p].size();i++){
int b=edge[p][i].to;
int c=edge[p][i].v;
if(!mark[b]&&dis[b]>dis[p]+c)
dis[b]=dis[p]+c;
}
}
if(dis[t]==inf)cout<<-1;
else cout<<dis[t];
}
时间复杂度 (O(n^2))
2.堆优化：
#include<bits/stdc++.h>
using namespace std;
#define inf 1e8
struct node{int to,v;};
bool operator<(node a,node b){return a.v>b.v;}
priority_queue<node>q;
vector <node> edge[10005];
int mark[10005],dis[10005];
int main(){
int n,m,s,t,a,b,c;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=n;i++)dis[i]=inf;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
edge[a].push_back(node<%b,c%>);
}
dis[s]=0;
q.push((node){s,0});
while(!q.empty()){
node tmp=q.top();q.pop();
int k=tmp.to;
if(mark[k])continue;
mark[k]=1;
for(int i=0;i<edge[k].size();i++){
int y=edge[k][i].to;
int v=edge[k][i].v;
if(dis[y]>dis[k]+v){
dis[y]=dis[k]+v;
q.push((node){y,dis[y]});
}
}
}
if(dis[t]==inf)dis[t]=-1;
printf("%d",dis[t]);
}
时间复杂度：(O((m+n)logn))
以前打堆优化好像有很多都在mark的地方打错了，但数据比较水。
提供一组hack：
4 4 1 4
1 2 1
1 3 2
2 4 6
3 4 2
输出:4
- bellmanford:时间复杂度 (O(n * m)),适用于负权边，可以判负环。
#include<bits/stdc++.h>
using namespace std;
struct node{int from,to,v;}edge[5005];
int n,m,dis[2505];
namespace bellmanford{
void solve(){
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].v);
memset(dis,127,sizeof(dis));
int inf=dis[0];
dis[1]=0;
for(int i=1;i<=n;i++){
bool flag=0;
for(int j=1;j<=m;j++){
int a=edge[j].from;
int b=edge[j].to;
int c=edge[j].v;
if(dis[a]==inf)continue;
if(dis[b]>dis[a]+c){
if(i<n)dis[b]=dis[a]+c;
flag=1;
}
}
if(!flag)break;
}
if(dis[n]==inf)puts("-1");
else cout<<dis[n];
}
}
int main(){
scanf("%d%d",&n,&m);
bellmanford::solve();
}
如果想要判负环的话，就可以把最外面那层循环变成 (2 * n)，如果 (i > n)后还有被更新的话就说明存在负环。
- SPFA: 关于SPFA，他已经死了，一个点可以重复入队，是bellmanford的队列优化，复杂度比较神奇，可能会被卡成 (n * m)。
#include<bits/stdc++.h>
using namespace std;
#define inf 1e8
struct node{int to,v;};
vector <node> edge[10005];
int dis[10005],isin[10005],num[10005];
queue<int>q;
int main(){
int n,m,s,t,a,b,c;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=n;i++)dis[i]=inf;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
edge[a].push_back(node<%b,c%>);
}
dis[s]=0;
q.push(s);isin[s]=1;num[s]=1;
while(!q.empty()){
int nw=q.front();q.pop();isin[nw]=0;
for(int i=0;i<edge[nw].size();i++){
int y=edge[nw][i].to,v=edge[nw][i].v;
if(dis[y]>dis[nw]+v){
dis[y]=dis[nw]+v;
if(isin[y])continue;
isin[y]=1;
q.push(y);
num[y]++;
if(num[y]>n){puts("有负环");return 0;}
}
}
}
if(dis[t]==inf)dis[t]=-1;
printf("%d",dis[t]);
}
记得pop的时候要标记一下它已经不在队列里了。
- Floyd：最暴力的最短路，时间复杂度(O(n^3))，可以求出任意两个点之间的最短路，也是最短的，代码最好记的。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dis[105][105];
void Floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
int main(){
int a,b,c;
scanf("%d%d",&n,&m);
memset(dis,0x3f,sizeof(dis));
int inf=dis[0][0];
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
dis[a][b]=min(dis[a][b],c);
}
for(int i=1;i<=n;i++)dis[i][i]=0;
Floyd();
if(dis[1][n]==inf)dis[1][n]=-1;
printf("%d",dis[1][n]);
}
三个循环中，k的含义是用k个节点联通两个点。