最短路径模板

堆优化的Dijkstra

typedef pair<int, int> P;   //first为边的权值，second为点的编号
const int N = 100005;
int dis[N];
vector<P>e[N];  //first为点的编号, second为边的权值
priority_queue<P, vector<P>, greater<P> >q;
void dij(int s)
{
    for (int i = 1; i <= N; ++i)    dis[i] = 0xffffff;
    dis[s] = 0;
    while (!q.empty())  q.pop();
    q.push(P(0, s));
    while (!q.empty())
    {
        P c = q.top(); q.pop();
        if (dis[c.second] < c.first)
            continue;
        for (int i = 0; i < e[c.second].size(); ++i)
        {
            int v = e[c.second][i].first;
            int w = e[c.second][i].second;
            if (dis[v] > c.first + w)
            {
                dis[v] = c.first + w;
                q.push(P(dis[v], v));
            }
        }
    }
}

普通Dijkstra

const int N = 5005;
bool book[N];
int dis[N];
int e[N][N];    //e最开始要初始化为0xffffff,e[i][i]设为0
void dij(int s)
{
    book[s] = true;
    for (int i = 1; i <= N; ++i)
        dis[i] = e[s][i];
    for (int i = 1; i < N; i++)
    {
        int u, min = 0xffffff;
        for (int j = 1; j <= n; j++)
            if (!book[j] && min > dis[j])
            {
                min = dis[j];
                u = j;
            }
        book[u] = 1;
        for (int v = 1; v <= n; v++)
            if (e[u][v] != 0xffffff && dis[v] > dis[u] + e[u][v])
                dis[v] = dis[u] + e[u][v];
    }
}

SPFA

const int M = 250005;
const int N = 100005;
struct edge
{
    int to, next, w;
}e[M << 1];
int cnt, head[N]
bool vis[N];
void spfa(int s, long long d[])
{
    for (int i = 0; i < n; ++i) d[i] = 0xfffffff;
    memset(vis, false, sizeof(vis));
    queue<int>q;
    d[s] = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            int w = e[i].w;
            if (d[v] <= d[u] + w)   continue;
            d[v] = d[u] + w;
            if (!vis[v])
            {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}