zju2281 -- way to freedom(a).cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2281 -- Way to Freedom
// Algorithm    Modified Dijkstra (DP)
// Complexity   O (NlogN + M)
// Author       LoveShsean
#include <stdio.h>
#include <string.h>

#define maxn 100100
#define maxm 2001000
#define inf 2100000000
#define min(a,b) (a<b?a:b)

int N, ps [maxn], heap [maxn], len, value [maxn], mk [maxn], nbs [maxn];
int M, ev [maxm], ew [maxm], next [maxm], ans, src, dst;

bool init ();
void solve ();
void out ();

int getmin ();
void update (int);

int main ()
{
    while (init ())
    {
        solve ();
        out ();
    }
    return 0;
}

bool init ()
{
    int i, j, u, v, w;
    if (scanf ("%d%d", &N, &j) != 2) return false;

    memset (nbs, 0, sizeof (nbs));
    for (i = M = 0; i < j; i ++)
    {
        scanf ("%d%d%d", &u, &v, &w);
        next [++ M] = nbs [u]; nbs [u] = M; ev [M] = v; ew [M] = w;
        next [++ M] = nbs [v]; nbs [v] = M; ev [M] = u; ew [M] = w;
    }
    scanf ("%d%d", &src, &dst);
    return true;
}

void solve ()
{
    int i, j, u, v;
    for (i = 1; i <= N; i ++) value [i] = 0, mk [i] = ps [i] = 0;
    value [src] = inf; heap [len = 1] = src; ps [src] = 1;
    while (!mk [dst])
    {
        if (!len) break;
        u = getmin (); mk [u] = 1;
        for (j = nbs [u]; j; j = next [j])
        {
            v = ev [j];
            if (!mk [v] && value [v] < min (value [u], ew [j]))
            {
                if (ps [v] == 0) { heap [++ len] = v; ps [v] = len; }
                value [v] = min (value [u], ew [j]);
                update (v);
            }
        }
    }
    ans = value [dst];
}

void out ()
{
    printf ("%d\n", ans);
}

int getmin ()
{
    int res = heap [1], p = 1, q = 2, r = heap [len --];
    while (q <= len)
    {
        if (q < len && value [heap [q + 1]] > value [heap [q]]) q ++;
        if (value [heap [q]] > value [r])
        {
            ps [heap [q]] = p;
            heap [p] = heap [q];
            p = q; q = p << 1;
        } else break;
    }
    heap [p] = r; ps [r] = p;
    return res;
}

void update (int r)
{
    int q = ps [r], p = q >> 1;
    while (p && value [heap [p]] < value [r])
    {
        ps [heap [p]] = q; heap [q] = heap [p];
        q = p; p = q >> 1;
    }
    heap [q] = r; ps [r] = q;
}