最短路专题整理

模板

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;
                }
            }
    }
}

模板二(链式前向星+优先队列优化)

主要优化在重边。因为使用了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; }
            }
        }
    }
}

A - Til the Cows Come Home(POJ 2387)

题意

给出n个点和m条边,求从1n的最短路。

思路分析

最短路裸题。如果用邻接表Dijkstra的话需要判重边。
FloydBellman-ford不需要。
我用的是链式前向星+Dijkstra,所以也可以不判重。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 4005;

int T,N;
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[maxn];

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));
            }
        }
    }
}

int main(){
    init();
    cin >> T >> N;
    while (T--){
        int u, v, d;
        cin >> u >> v >> d;
        addedge(u, v, d);
        addedge(v, u, d);
    }
    Dijkstra(1);
    cout << dis[N] << endl;
    return 0;
}

B - Heavy Transportation(POJ 1797)

题意

给出从1城到n城的每条路的最大载重量,求最大运货量。

思路分析

最短路的变形题,只需要改一下松弛操作就可以了。