最短路

Dijkstra

注意：不能处理负边权， 有负边权就换SPFA。

以下代码以HDOJ 1874(畅通工程续) 为例
简洁好理解的堆优化代码。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

typedef pair<int,int> pr;
const int maxn=205;
vector<pr> E[maxn];

int n, m;
int d[maxn];
void init() {
    for(int i=0; i<maxn; ++i) E[i].clear();
    for(int i=0; i<maxn; ++i) d[i]=1e9;
}

int main() {
    while(cin>>n>>m) {
        init();
        for(int i=0; i<m; ++i) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            E[x].push_back(make_pair(y,z));
            E[y].push_back(make_pair(x,z));
        }
        int s, t;
        scanf("%d%d", &s, &t);
        priority_queue<pr,vector<pr>,greater<pr> > Q;
        Q.push(make_pair(0,s));
        d[s]=0;
        while(!Q.empty()) {
            int now=Q.top().second;
            Q.pop();
            for(int i=0; i<E[now].size(); ++i) {
                int v=E[now][i].first;
                if(d[v]>d[now]+E[now][i].second) {
                    d[v]=d[now]+E[now][i].second;
                    Q.push(make_pair(d[v],v));
                }
            }
        }
        if(d[t]==1e9) printf("-1\n");
        else printf("%d\n", d[t]);
    }
}

也可不用greater函数，直接将每次放入队列的d[v]改成-d[v]即可。

SPFA

以下代码以HDOJ 1874(畅通工程续) 为例
注意有个inq数组来记录某个点是否已经在队列了，这是与dij不同的。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

const int maxn=205;
vector<pair<int, int> >E[maxn];

int n, m;
int d[maxn], inq[maxn];
void init() {
    for(int i=0; i<maxn; ++i) E[i].clear();
    for(int i=0; i<maxn; ++i) inq[i]=0;
    for(int i=0; i<maxn; ++i) d[i]=1e9;
}

int main() {
    while(cin>>n>>m) {
        init();
        for(int i=0; i<m; ++i) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            E[x].push_back(make_pair(y,z));
            E[y].push_back(make_pair(x,z));
        }
        int s, t;
        scanf("%d%d", &s, &t);
        queue<int> Q;
        Q.push(s);
        d[s]=0;
        inq[s]=1;
        while(!Q.empty()) {
            int now=Q.front();
            Q.pop();
            inq[now]=0;
            for(int i=0; i<E[now].size(); ++i) {
                int v=E[now][i].first;
                if(d[v]>d[now]+E[now][i].second) {
                    d[v]=d[now]+E[now][i].second;
                    if(inq[v]==1) continue;
                    inq[v]=1;
                    Q.push(v);
                }
            }
        }
        if(d[t]==1e9) printf("-1\n");
        else printf("%d\n", d[t]);
    }
}

Floyd

总所周知 简单粗暴
以下为floyd的路径保存问题代码， 并且附带倒序输出路径
若想要正序输出， 则先将路径弄到栈里面再弹出

void floyd() {
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            if(d[i][j]==inf) path[i][j]=-1;
            else path[i][j]=i;
        }
    }
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            for(int k=0; k<n; ++k) {
                if(!(d[i][k]==inf||d[k][j]==inf)&&d[i][k]+d[k][j]<d[i][j]) {
                    d[i][j]=d[i][k]+d[k][j];
                    path[i][j]=path[k][j];
                }
            }
        }
    }
}
void printpath(int from, int to) {
    printf("%d ", to);
    while(path[from][t]!=from) {
        printf("%d ", path[from][to]);
        to=path[from][to];
    }
}

Bellman-Ford

SPFA就是这个算法的队列优化， 所以暂时不写了。