算法提高课汇总

模型抽象

• $T$个城镇: 图的$T$个顶点.

• 双向道路: 无向图.

• 通过费用: 边的权值.

• 起点$T_s$到终点$T_e$的最小费用: 权值最小的路径 --> 单源最短路.

代码实现

问题数据规模很小, 且没有负权边, 可用的算法很多.

$Spfa()$ $T(n, m) = O(m)\sim O(nm)$

#include <cstring>
#include <iostream>

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;

int n, m, s, t;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N]; //st[u] = true: 顶点u已经在循环队列q中

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++ ;
}

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    int hh = 0, tt = 0;
    q[tt ++] = s; st[s] = true;
    while( hh != tt )
    {
        int u = q[hh ++];
        st[u] = false; //出队列
        if( hh == N )   hh = 0;
        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( dist[v] > dist[u] + w[i] )
            {
                dist[v] = dist[u] + w[i];
                if( !st[v] )
                {
                    q[tt ++] = v;
                    st[v] = true;
                    if( tt == N )   tt = 0;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> s >> t;
    memset(h, -1, sizeof h);
    for( int i = 0; i < m; i ++ )
    {
        int u, v, c;
        cin >> u >> v >> c;
        add(u, v, c); add(v, u, c);
    }

    spfa();
    cout << dist[t] << endl;

    return 0;
}