ping(普通bfs，优先队列bfs).cpp

杭电acm解题报告2001---2099.

//状态的hash[节点标号][路径数]＝最小花费
//凡是搜索，除了数据量小以外，其它的都需要状态的保存
#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

#define Min(x,y) ((x)<(y)?(x):(y))
int map[1100][1100];
int hash[1100][11];
int n,m,t,mmin;


struct inf {
    int pos,cost,d;
    bool operator < (const inf &a) const {
        return cost > a.cost;
    }
};
priority_queue<inf> PQ;
queue<inf> SQ;
void bfs()
{
    while (!PQ.empty()) {
        PQ.pop();
    }
    memset(hash,0,sizeof(hash));
    
    inf s, g;
    s.cost = s.pos = s.d = 0;
    PQ.push(s);
    
    while (!PQ.empty()) {
        int size = PQ.size();
        while (size --) {
            s = PQ.top();
            PQ.pop();
            
            if (s.d > 10) {
                continue ;
            }
            if (s.pos == t) {
                mmin = Min(mmin, s.cost);
                return ;
            }
            
            for (int i=1;i<n;i++) {
                if (i!=s.pos && map[s.pos][i] != 0) {
                    g = s;
                    g.cost += map[s.pos][i];
                    g.pos = i;
                    g.d ++;
                    if (hash[g.pos][g.d] !=0 && hash[g.pos][g.d] < g.cost) {
                        continue ;
                    }
                    hash[g.pos][g.d] = g.cost;    
                    PQ.push(g);
                }
            }
        }//size
    }
}

void bfs2()
{
    while (!SQ.empty()) {
        SQ.pop();
    }
    memset(hash,0,sizeof(hash));
    
    inf s, g;
    s.cost = s.pos = s.d = 0;
    SQ.push(s);
    
    while (!SQ.empty()) {
        
        s = SQ.front();
        SQ.pop();
        
        if (s.d > 10) {
            return ;
        }
        if (s.pos == t) {
            mmin = Min(mmin, s.cost);
            continue ;
        }
        
        for (int i=1;i<n;i++) {
            if (i!=s.pos && map[s.pos][i] != 0) {
                g = s;
                g.cost += map[s.pos][i];
                g.pos = i;
                g.d ++;
                if (hash[g.pos][g.d] !=0 && hash[g.pos][g.d] < g.cost) {
                    continue ;
                }
                else {//普通bfs要注意优化剪枝
                    for (int j=g.d-1;j>0;j--) {
                        if (hash[g.pos][j]!=0 && g.cost >= hash[g.pos][j]) {
                            break;
                        }
                    }
                    if (j != 0) {
                        continue;
                    }    
                }
                hash[g.pos][g.d] = g.cost;            
                SQ.push(g);
            }
        }
        
    }
}

int main()
{
    while (scanf("%d %d %d",&n,&m,&t)==3) {
        if (n == 0) {
            break;
        }
        memset(map,0,sizeof(map));
        
        for (int i=0;i<m;i++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if (map[a][b] == 0) {
                map[a][b] = map[b][a] = c;
            }
            else { 
                map[a][b] = Min(map[a][b] , c);
            }
        }
        mmin = 0x7fffffff;
        bfs();//优先队列
        //bfs2();//普通bfs
        if (mmin != 0x7fffffff) {
            printf("%d\n",mmin);
        }
        else {
            printf("no\n");
        }
    }
}