最短路模板整理

Dijkstra

模板一（map数组模拟邻接表）

处理小图速度相对较快。
内存占用较小，对重边优化较差。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;

int map[maxn][maxn];
int pre[maxn],dis[maxn];
bool vis[maxn];
int n,m;

void Dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;++i)
    {
        dis[i]=map[s][i];
        pre[i]=s;
    }
    dis[s]=0;
    vis[s]=true;
    for(int i=2;i<=n;++i)
    {
        int mindist=INF;
        int u=s;
        for(int j=1;j<=n;++j)
            if((!vis[j])&&dis[j]<mindist)
            {
                u=j;
                mindist=dis[j];
            }
        vis[u]=true;
        for(int j=1;j<=n;++j)
            if((!vis[j])&&map[u][j]<INF)
            {
                if(map[u][j]+dis[u]<dis[j])
                {
                    dis[j]=map[u][j]+dis[u];
                    pre[j]=u;
                }
            }
    }
}
int main(){
    cin >> m >> n;
    for (int i=1; i <=n;i++)
        for (int j=1;j <=n;j++){
            if (i == j) map[i][j] = 0;
            else map[i][j] = map[j][i] = INF;
        }
    while (m--) {
        int start, end, len;
        cin >> start >> end >> len;
        map[start][end] = len;
        map[end][start] = len;
    }
    cout << map[2][5] << endl;
    Dijkstra(1);
    cout << dis[n] << endl;
    return 0;
}

模板二（链式前向星+优先队列优化）

主要优化在重边。因为使用了STL所以占用内存和速度相对较慢。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;
const int INF=0x3f3f3f3f;

struct node
{
    int d,u;
    friend bool operator<(node a,node b)
    {
        return a.d>b.d;
    }
    node(int dist,int point):d(dist),u(point){}
};

struct Edge
{
    int to,next;
    int dist;
}edge[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];

void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}

void addedge(int u,int v,int d)
{
    edge[tot].to=v;
    edge[tot].dist=d;
    edge[tot].next=head[u];
    head[u]=tot++;
}

void Dijkstra(int s)
{
    priority_queue<node> q;
    memset(dis,0x3f,sizeof(dis));
    memset(pre,-1,sizeof(pre));
    dis[s]=0;
    while(!q.empty())
        q.pop();
    node a(0,s);
    q.push(a);       //起点入队列
    while(!q.empty())
    {
        node x=q.top();
        q.pop();
        if(dis[x.u]<x.d)   //最短路已找到
            continue;
        for(int i=head[x.u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[x.u]+edge[i].dist)
            {
                dis[v]=dis[x.u]+edge[i].dist;
                pre[v]=x.u;
                q.push(node(dis[v],v));
            }
        }
    }
}

模板三（结构体内置方法）

因为使用了链式前向星所以不担心重边。
其中还使用了快读方法，所以很快。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;

const int N = 1005;
const int M = 1005;
const int INF = 0x3f3f3f3f

struct Graph{
    struct Edge{
        int v, w, next;
    }edge[M];
    int ehead[N];
    void init(){
        memset(ehead, -1, sizeof(ehead))
    }
    inline void addedge(int u, int v, int w){
        edge[ecnt] = {v, w, ehead[u]};
        ehead[u] = ecnt++;
    }
    int dist[N];
    bool vis[N];
    void Dijkstra(int s){
        memset(dist, INF, sizeof(dist));
        memset(vis, 0, sizeof(vis));
        priority_queue<pair<int, int> > q;
        q.push(make_pair(-(dist[s] = 0), s));
        while(q.size()){
            int u = q.top().second; q.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (int i = ehead[u]; ~i; i = edge[i].next){
                int v = edge[i].v;
                if (vis[v]) continue;
                int ndist = dist[u] + edge[i].w;
                if (ndist < dist[v]) q.push(make_pair(-(dist[v] = ndist), v));
            }
        }
    }
}g1, g2;

int Input(){
    char c;
    for (c = getchar(); c<'0' || c>'9'; c = getchar());
    int a = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        a = a*10 + c - '0';
    return a;
}

Floyd

代码很短，时间复杂度很高（O(n^3)）。

void floyd(){
    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                if (map[i][j] > map[i][k] + map[k][j]) //松弛
                    map[i][j] = map[i][k] + map[k][j];
}

Bellman-Ford

模板一（链式前向星）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct Edge{
    int u, v;
    double r, c;
}edge[maxn*2];

double mostMoney[maxn];
int n, m, s;
double v;
int tot;

void addedge(int u, int v, double r, double c){
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].r = r;
    edge[tot++].c = c;
}

bool relax(int n){
    double temp = (mostMoney[edge[n].u] - edge[n].c)*edge[n].r;
    if (temp > mostMoney[edge[n].v]){
        mostMoney[edge[n].v] = temp;
        return true;
    }
    return false;
}

bool bellman_ford(){
    bool flag;
    for (int i=0; i<n; i++) mostMoney[i] = 0.0;
    mostMoney[s] = v;
    for (int i=0; i<n-1; ++i){
        flag = false;
        for (int j=0; j<tot; ++j)
            if (relax(j)) flag = true;
        if (mostMoney[s] > v) return true;
        if (!flag) return false;
    }
    for (int i=0; i<tot; ++i){
        if (relax(i)) return true;
    }
    return false;
}

模板二

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

const int INF=0x3f3f3f3f;
struct Edge{
    int u,v; //起点、终点
    int dist; //长度
}edge[maxn];

int dis[maxn]; //最短距离数组
int n, m; //结点数、边数

bool Bellman_ford(int s){
    memset(dis, INF, sizeof(dis));
    dis[s]=0;
    for(int k=1; k<n; ++k){ //迭代n-1次
        for(int i=0; i<m; ++i){  //检查每条边
            int x = edge[i].u, y = edge[i].v;
            if(dis[x] < INF)
                dis[y] = min(dis[y], dis[x] + edge[i].dist);
        }
    }
    bool flag=1;
  for(int i=0; i<m; ++i){   //判断是否有负环
        int x = edge[i].u, y = edge[i].v;
        if(d[y] > d[x] + edge[i].dist){
            flag = 0; break;
        }
    }
    return flag;
}

SPFA

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1000005
using namespace std;
const long long INF = 0xffffffff;

int Input(){
    char c;
    for (c = getchar(); c<'0' || c>'9'; c = getchar());
    int a = c - '0';
    for (c = getchar(); c>='0' && c<='9'; c = getchar()) a = a * 10 + c - '0';
    return a;
}

int n, m;
struct edge{
    int e, next, w;
}edge[2][maxn];

long long dis[maxn], ans;
int head[2][maxn], vis[maxn];

inline void spfa(int x){
    for (int i=1; i<=n; i++){
        dis[i] = 0xffffffff;
        //cout << dis[i] << endl;
    }
    memset(vis, 0, sizeof(vis));
    
    queue<int> q;
    int a, b;
    
    q.push(1);
    vis[1] = 1;
    dis[1] = 0;
    
    while(!q.empty()){
        a = q.front(); q.pop();
        vis[a] = 1;
        
        for (int i=head[x][a]; i != -1; i=edge[x][i].next){
            b = edge[x][i].e;
            if (dis[b] > dis[a] + edge[x][i].w){
                dis[b] = dis[a] + edge[x][i].w;
                if (!vis[b]) { q.push(b); vis[b] = 1; }
            }
        }
    }
}