最短路
单源最短路
Dijkstra算法
边权非负
# include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Dijkstra{
#define MAXN 1234
#define INF 0x3f3f3f3f
int n,m,s,t;
int dis[MAXN],M[MAXN][MAXN];
bool vis[MAXN];
void init()
{
scanf("%d%d%d%d",&n,&m,&s,&t);//点个数，路个数，起点，终点
int u,v,c;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j) M[i][j]=INF;
}
}
for(int k=0;k<m;k++){
scanf("%d%d%d",&u,&v,&c);
M[u][v]=M[v][u]=min(M[u][v],c);
}
}
void solve()
{
memset(vis,0,sizeof(vis));
fill(dis+1,dis+n+1,INF);
dis[s]=0;
for(int i=1;i<=n;i++){
int x,minn=INF;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<=minn) minn=dis[x=j];
}
vis[x]=1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]>dis[x]+M[x][j]) dis[j]=dis[x]+M[x][j];
}
}
printf("%d\n",dis[t]);
}
};
Dijkstra Dij;
int main()
{
Dij.init();
Dij.solve();
return 0;
}
堆优化dij
# include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
struct Edge{
int u,v,d;
Edge(int uu,int vv,int dd):u(uu),v(vv),d(dd){}
};
struct Dijkstra{
#define MAXN 123456
#define INF 0x3f3f3f3f
int n,m;
int s,t;
vector<Edge> edges;
vector<int> G[MAXN];
bool done[MAXN];
int d[MAXN],p[MAXN];
void init()
{
for(int i=1;i<=n;i++) G[i].clear();
edges.clear();
scanf("%d%d%d%d",&n,&m,&s,&t); //n地点个数，m道路条数，s入口,t出口
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
}
void AddEdge(int u,int v,int d)
{
edges.push_back(Edge(u,v,d));
int m=edges.size();
G[u].push_back(m-1); //链接u的一共由几条边
}
void solve()
{
priority_queue<P,vector<P>,greater<P> >Q;
for(int i=1;i<=n;i++) d[i]=INF;
d[s]=0;
memset(done,0,sizeof(done));
Q.push(P(0,s));
while(!Q.empty()){
P x=Q.top(); Q.pop();
int u=x.second;
if(done[u]) continue;
done[u]=true;
for(int i=0;i<G[u].size();i++){
Edge &e=edges[G[u][i]];
if(!done[e.v]&&d[e.v]>d[u]+e.d){
d[e.v]=d[u]+e.d;
p[e.v]=G[u][i];
Q.push(P(d[e.v],e.v));
}
}
}
printf("%d\n",d[t]);
}
};
Dijkstra Dij;
int main()
{
Dij.init();
Dij.solve();
return 0;
}
Bellman_ford
图中出现权值为负的边
# include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef pair<int,int> P;
struct Edge{
int from,to,dist;
Edge(int u,int v,int d):from(u),to(v),dist(d){
}
};
struct Bellman_ford{
#define MAXN 1234567
bool inq[MAXN];//用来记录入队次数
int cnt[MAXN],d[MAXN],p[MAXN];
//cnt来记录入队次数，大于n就退出，d用来记录最短距离，p用来记录路径
int n,m,s,t;
vector<Edge> edges;
vector<int> G[MAXN];
void AddEdge(int from,int to,int dist){
edges.push_back(Edge(from,to,dist));
edges.push_back(Edge(to,from,dist));
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
void init()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&c);
AddEdge(u,v,c);
}
}
bool bellman_ford()
{
queue<int> Q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) d[i]=INF;
d[s]=0;
inq[s]=true;
Q.push(s);
while(!Q.empty()){
int u=Q.front();
Q.pop();
inq[u]=false;
for(int i=0;i<G[u].size();i++){
Edge &e=edges[G[u][i]];
if(d[u]<INF&&d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
if(!inq[e.to]){
Q.push(e.to);
inq[e.to]=true;
if(++cnt[e.to]>n) return false;
}
}
}
}
printf("%d\n",d[t]);
}
};
Bellman_ford bell;
int main()
{
bell.init();
bell.bellman_ford();
return 0;
}
多源最短路
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
struct Floyd{
//复杂度 O(n^3)
#define MAXN 300
int d[MAXN][MAXN];
int n,m;
void init()
{
scanf("%d%d",&n,&m);//n为地点个数 m道路条数
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j) d[i][j]=INF;
}
}
int u,v,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&c);
d[u][v]=d[v][u]=min(d[v][u],c);
}
}
void floyd()
{
for(int k=1;k<=n;k++){//中间经过的点
for(int i=1;i<=n;i++){//起点
for(int j=1;j<=n;j++){//终点
if(d[i][k]<INF&&d[j][k]<INF) d[i][j]=min(d[i][j],d[i][k]+d[j][k]);
}
}
}
}
void print()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d%c",d[i][j]," \n"[j==n]);
}
}
}
};
Floyd floyd;
int main()
{
floyd.init();
floyd.floyd();
floyd.print();
return 0;
}