经济基础决定上层建筑

菜鸡的 新认知

细节上的差异还是很考验理解呢… 我还是太菜了… noip2017的划水似乎能预见了呢…
dijk的堆优化毕竟只是堆优化呢… 在DYYZ没学BF就学SPFA怕是一个很大的失误吧… 学优化前还是应该掌握好本体啊…
仅仅从优化的角度来看dijk的代码就好理解了呢… 优先队列的作用仅仅是找到 d 最小的一个点… v 数组的改变完全没有变呢…
SPFA是更新后就把当前的点入队…所以在队列里这个数组在入队后就设为true了…
而dijk是确定当前的点是最短路最小的时候才把v设成true
看来我还是菜啊… 今年爆零也不会太出乎意料吧… 顺理成章啊…

沙茶的 代码

struct edg
{
    int from;
    int to;
    int cost;
    int next;
};
struct node
{
    int d;
    int bh;
};
struct cmp
{
    bool operator () (node a, node b)
    {
        return a.d > b.d;
    }
};
struct dijk
{
    int n;
    int m;

    bool v[MAXN];

    edg b[MAXM];
    int g[MAXN];
    int cntb;

    node a[MAXN];
    int s, t;

    void init()
    {
        memset(g, 0, sizeof(g));
        cntb = 0;
        scanf("%d%d%d", &n, &m, &s);
        for (int i = 1; i <= n; i++)
            a[i].bh = i;
        int srx, sry, srz;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &srx, &sry, &srz);
            ade(srx, sry, srz);
        }
    }

    void ade(int fr, int to, int co)// add an edge
    {
        b[++cntb].from = fr;
        b[cntb].to = to;
        b[cntb].cost = co;
        b[cntb].next = g[fr];
        g[fr] = cntb;
    }

    void DD()// Emmmm...
    {
        priority_queue<node, vector <node>, cmp> q;
        memset(v, false, sizeof(v));
        for (int i = 1; i <= n; i++)
        {
            a[i].d = INF;
        }
        a[s].d = 0;
        q.push(a[s]);
        node dq;
        while(!q.empty())
        {
            dq = q.top();    q.pop();
            if (v[dq.bh])
            continue;
            v[dq.bh] = true;
            for (int j = g[dq.bh]; j; j = b[j].next)
            {
                if (a[b[j].to].d > dq.d + b[j].cost)
                {
                    a[b[j].to].d = dq.d + b[j].cost;
                    q.push(a[b[j].to]);
                }
            }
        }
    }
}

By 被吓哭的 Cansult