模板 – 最短路

Dijkstra

[ CF 20C – 模板 ]
\Omicron(V \log V + E)

struct disn_t {
    lli v;
    lli w;
    disn_t() { }
    disn_t(lli iv, lli iw) : v(iv), w(iw) { }
    friend bool operator <(const disn_t& a, const disn_t& b) {
        return a.w > b.w;
    }
};

lli dis[maxn];
bool vis[maxn];
inline void dij(lli s) {
    priority_queue<disn_t> q;
    dis[s] = 0;
    q.push(disn_t(s, 0));
    while (!q.empty()) {
        lli u = q.top().v;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (lli i = 0; i < mp[u].size(); ++i) {
            lli v = mp[u][i].v;
            lli w = mp[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(disn_t(v, dis[v]));
            }
        }
    }
}

SPFA

[ 络谷 P3385 ]
\Omicron(VE)

lli dis[maxn];
bool vis[maxn];
inline bool spfa() {
    dis[1] = 0;
    queue<lli> q;
    q.push(1);
    while (!q.empty()) {
        lli u = q.front();
        q.pop();
        vis[u] = false;
        for (lli i = 0; i < mp[u].size(); ++i) {
            lli v = mp[u][i].v;
            lli w = mp[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}