poj-3159很神奇的一题-差分约束+spfa

这道题目和前面几篇思路一样，不用多说
 
问题是如果用spfa+队列，肯定tle，换为堆栈就可以了，这题目也就是从头不行，要从尾部开始，就是队列和栈的区别了。
 
总感觉这题有问题。正向超时，反向484ms。。。。
代码：
[cpp] 
#include <stdio.h> 
 
#define maxN 30005//最大边条数 
#define inf 0x7fffffff//最大距离 
 
struct Edge  
{ 
    int v, w, next; 
}edge[5 * maxN];//边集 
 
int dis[maxN]; 
bool vis[maxN]; 
int queue[30 * maxN]; 
int preEdge[maxN];//同一个顶点的前一条边 
 
int edgeNum,n,m; 
 
void addEdge(int u, int v, int w)//添加一条边 
{ 
    edge[edgeNum].v = v; 
    edge[edgeNum].w = w; 
    edge[edgeNum].next = preEdge[u]; 
    preEdge[u] = edgeNum ++; 
} 
 
void spfa()//spaf算法 
{ 
    int head = 0, tail = 1, top = 0; 
    for (int i = 1; i <= n; ++ i) 
    { 
        dis[i] = inf; 
    } 
    //queue[head] = 1; 
    queue[top ++] = 1; 
    dis[1] = 0; 
    while (top/*head != tail*/) 
    { 
        //int u = queue[head]; 
        int u = queue[-- top]; 
        vis[u] = true; 
        for (int p = preEdge[u]; p != 0; p = edge[p].next) 
        { 
            int v = edge[p].v; 
            if (dis[v] > dis[u] + edge[p].w) 
            { 
                dis[v] = dis[u] + edge[p].w; 
                if (!vis[v]) 
                { 
                    vis[v] = true; 
                    queue[top ++] = v; 
                    //queue[tail] = v; 
                    /*tail ++;
                    if (tail == maxN)
                    {
                        tail = 0;
                    }*/ 
                } 
            } 
        } 
        vis[u] = false; 
        /*head ++;
        if (head == maxN)
        {
            head = 0;
        }*/ 
    } 
} 
 
int main() 
{ 
    scanf("%d%d", &n, &m); 
    edgeNum = 1; 
    while (m --) 
    { 
        int u, v, w; 
        scanf("%d%d%d", &u, &v, &w); 
        addEdge(u, v, w); 
    } 
    spfa(); 
    printf("%d\n", dis[n]); 
    return 0; 
} 
作者：zhang20072844

补充：软件开发 , C++ ,