Poj 3159(差分制約システム、SPFA+スタック、Dij+heap)

最初の差分制約システムの問題をした後、熱いうちに鉄を打ってからもう一つ来ます.この問題が純粋な短距離問題カード時間の問題だとは思わなかった.問題の意味を理解するには注意すべき点があり、私は最初はSPFA(1)、dis[n]、再SPFA(n)、dis[1]を得て、両者の大きな値を取った.実際には前者だけでよいが,dis[n]は答えである.
   1. 最初はSPFAのキュー実装を直接書いたばかりで、タイムアウトに違いない.
   2. スタックがSPFAを実現するのが早いと聞いて、またスタックに書き換えたが、結局タイムアウトした.これはおかしい.discussはスタックが通れると言っているだろう.私は標準的な図の隣接テーブルストレージ、つまりチェーンテーブルで実現していますが、他の人が使っている配列でシミュレーションしているのを見て、配列シミュレーションが速いのではないかと思います.また変わったのか、悲劇がタイムアウトしたのか.
   3. また、私のコードは他の人とは少し違うことに気づきました.私が追加した辺はadd(b,a,k)で、人はadd(a,b,k)ですが、影響はないと思います.一つの意味です.私はadd(a,b,k)に変更してAC(500+MS)にしました.
   4. 逆に私の元の標準図の隣接テーブルストレージに変更して、またタイムアウトしました.これはちょっと納得できませんが、ポインタの操作の効率が高いと言っているのではないでしょうか.どうしてこれが体現できないのか、ましてこの時間の上限は1.5 Sで、配列シミュレーションで0.5 Sで、チェーンテーブルでタイムアウトします....本当に納得できない.
   5. discussでは「点が少なくて辺が多く、Dijを使うべきだ」という問題がありますが、普通のDij時間の複雑さは(n^2)肯定タイムアウトなので、「優先キュー」でサイクルごとに最小のdis[i]値を探す過程を実現するには、c++のSTLのpriority_queue.悲劇的なのは私がc.なので、自分で優先列を実現するために山を書かなければなりません.長い間研究して,書き上げた.悲劇は直接だ
   6. 葛藤.....葛藤する......バグを探して...探してる...探して...やっとc言語の同胞を見つけた.コードを分析してみると確かに発見しにくい脆弱性がある:最近の点、すなわち小根スタック中のルートQ[1]を見つけるたびに、変更点をキューから削除し、このとき新しいスタック、すなわちHeapAdjust(1)と、(この過程で私のプログラムは問題ありません)、この点に隣接する点を緩和して、緩和した後にdis[]が変化して、再びスタックを更新しなければなりません(これは私が落としました).....バグand AC(600+MS)を修正する.oh...yes...
   7. この問題はまた30以上のSubmitに貢献しました...
 
マイSPFA(スタック実装):

#include <stdio.h>  
#include <stdlib.h>  
#define INF 100000000  
struct Edge  
{  
    int e, v;  
} edge[150005];  
int neg;  
int node[30005];  
int next[150005];  
int n;  
int dis[30005], vst[30005];  
int Q[30005];  
void add(int s, int e, int v)  
{  
    edge[neg].e = e;  
    edge[neg].v = v;  
    next[neg] = node[s];  
    node[s] = neg++;  
}  
int relax(int s, int e, int v)  
{  
    if (dis[s]+v < dis[e])  
    {  
        dis[e] = dis[s]+v;  
        return 1;  
    }  
    return 0;  
}  
/*           */  
int SPFA(int s0)  
{  
    int i, t, p, top;  
    for (i=1; i<=n; i++)  
        dis[i] = INF;  
    dis[s0] = 0;  
    Q[0] = s0;  
    top = 1;  
    vst[s0] = 1;  
    while (top)  
    {  
        t = Q[--top];  
        p = node[t];  
        while (p != -1)  
        {  
            if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e])  
            {  
                Q[top++] = edge[p].e;  
                vst[edge[p].e] = 1;  
            }  
            p = next[p];  
        }  
        vst[t] = 0;  
    }  
    return 1;  
}  
int main()  
{  
    int m, k, a, b;  
    memset(node, -1, sizeof(node));  
    scanf("%d %d", &n, &m);  
    while (m--)  
    {  
        scanf("%d %d %d", &a, &b, &k);  
        add(a, b, k);  
    }  
    SPFA(1);  
    printf("%d/n", dis[n]);  
}

私のDij+heap:

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#define MAXV 30005  
#define MAXE 150005  
#define INF  1000000000  
struct Edge  
{  
    int e, v;  
} edge[MAXE];  
int n, neg;  
int dis[MAXV], vst[MAXV];  
int node[MAXV], next[MAXE];  
int Q[MAXV];  
int index[MAXV];  
void add(int s, int e, int v)  
{  
    edge[neg].e = e;  
    edge[neg].v = v;  
    next[neg] = node[s];  
    node[s] = neg++;  
}  
void swap(int x, int y)  
{  
    int t;  
    t = Q[x];  
    Q[x] = Q[y];  
    Q[y] = t;  
    index[Q[x]] = x;  
    index[Q[y]] = y;  
}  
void heapAdjust(int root)  
{  
    int l, r, min;  
    l = 2*root;  
    r = 2*root+1;  
    min = root;  
    if (l <= Q[0] && dis[Q[l]] < dis[Q[min]])  
        min = l;  
    if (r <= Q[0] && dis[Q[r]] < dis[Q[min]])  
        min = r;  
    if (min != root)  
    {  
        swap(root, min);  
        heapAdjust(min);  
    }  
}  
void  buildHeap()  
{  
    int i;  
    Q[0] = n;  
    for (i=1; i<=n; i++)  
    {  
        Q[i] = i;  
        index[i] = i;  
    }  
    for (i=n/2; i>=1; i--)  
        heapAdjust(i);  
}  
/*   dis[Q[root]]   ,    , Q[root]              */  
void update(int root)  
{  
    while (root/2 && dis[Q[root]] < dis[Q[root/2]])  
    {  
        swap(root, root/2);  
        root = root/2;  
    }  
}  
int getMin()  
{  
    int min;  
    min = Q[1];  
    Q[1] = Q[Q[0]];  
    Q[0]--;  
    index[Q[1]] = 1;  
    heapAdjust(1);  
    return min;  
}  
/*  Dijkstra  ，         */  
void Dijkstra(int s0)  
{  
    int i, k, p;  
    for (i=1; i<=n; i++)  
        dis[i] = INF;  
    dis[s0] = 0;  
    buildHeap();  
    while (Q[0])  
    {  
        k = getMin();  
        vst[k] = 1;  
        p = node[k];  
        while (p != -1)  
        {  
            if (!vst[edge[p].e] && dis[k]+edge[p].v<dis[edge[p].e])  
            {  
                dis[edge[p].e] = dis[k]+edge[p].v;  
                update(index[edge[p].e]);  
                /* index         ,   dis[e],     , 
                             ,   e           , 
                     dis[e]    .                              */  
            }  
            p = next[p];  
        }  
    }  
}  
int main()  
{  
    int m, k, a, b;  
    memset(node, -1, sizeof(node));  
    scanf("%d %d", &n, &m);  
    while (m--)  
    {  
        scanf("%d %d %d", &a, &b, &k);  
        add(a, b, k);  
    }  
    Dijkstra(1);  
    printf("%d/n", dis[n]);  
    return 0;  
}