hdu_1385 逆向SPFA求字典序最小最短路

唉，被求最小的字典序搞死了，如果用dijkstra很好实现，但是用spfa就只有用逆向的写法了。

#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
const int maxn=1<<7;
const int inf=0x7fffffff;
int a[maxn][maxn];
int b[maxn];
int d[maxn];  
bool hash[maxn];   
int pre[maxn];     
int N,x,y,temp;
int out[maxn];
deque<int>q;
inline void init()
{   
    for(int i=1;i<=N;i++)
    {
        d[i]=inf;  
        pre[i]=inf;
        hash[i]=false;  
    }
    d[y]=0;
    q.clear();
    return ;
}
void spfa()
{
    q.push_front(y);    
    hash[y]=true;
    while(!q.empty())
    {
        temp=q.back();
        q.pop_back();
        for(int i=1;i<=N;i++)
        {
            if(-1 == a[i][temp] || i==temp)
            {
                continue;
            }    
            else
            {           
                if( d[temp] + b[i] + a[i][temp] < d[i] )
                {   
                    d[i]=d[temp] + b[i] + a[i][temp]; 
                    pre[i]=temp;
                    if(hash[i]==false)
                    {
                        q.push_front(i);
                        hash[i]=true;
                    }
                }
                else if( d[temp] + b[i] + a[i][temp] == d[i] )
                {
                    if(temp < pre[i])
                    {
                        pre[i]=temp;
                    }        
                }
            }
        }  
        hash[temp]=false;  
    } 
    out[0]=x;
    temp=0;
    while( pre[out[temp]] != inf )
    {
        out[temp+1]=pre[out[temp]];
        temp++;    
    }               
    printf("From %d to %d :\nPath: ",x,y);
    for(int i=0;i<temp;i++)
    {
        printf("%d-->",out[i]);
    }
    printf("%d\n",out[temp]);
    printf("Total cost : %d\n\n",d[x]-b[x]);
    return ;
}
int main()
{
    while(cin>>N && N)
    {      
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)   
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=N;i++)
        {
            cin>>b[i];
        }
        while(cin>>x>>y)
        {
            if(-1==x && -1==y)
            {
                break;
            }
            if(x!=y)        
            {
                init();
                spfa();     
            }
            else
            {
                printf("From %d to %d :\n",x,y);
                printf("Path: %d\n",x);
                printf("Total cost : 0\n\n");
            }
        }     
    }
    return 0;
}