【算法学习】分枝限界法（二）

//优先队列式分支限界法 解单源最短路径问题
//来源互联网 ，作者csdn zzzsdust 原文链接见后文 
#include <bits/stdc++.h>  //头文件中附带有优先队列 
using namespace std;
class MinHeapNode  //最小堆 
{
public:
    int id;
    int length; //从起始点 v 到点 id 的距离
public:
    friend bool operator < (const MinHeapNode &a, const MinHeapNode &b)   //运算符重载 
    {
        return a.length < b.length;
    }
    friend bool operator > (const MinHeapNode &a, const MinHeapNode &b)
    {
        return a.length > b.length;
    }
};
const int max_ = 0x3f3f3f;
int Graph[100][100];  //输入两点间距离 
int dist[100];    //到原点距离 
int pre[100];   //记录最短路径中的前一个点 
int n, m, v;
void OutPutPath(int i)   //输出到原点的最短路径 
{
    if(i == pre[i])
    {
        printf("%d", i);
        return;
    }
    else
    {
        OutPutPath(pre[i]);
        printf(" %d", i);
    }
}
void OutPut()
{
    for(int i = 1; i <= n; ++i)
    {
        if(i != v)
        {
            printf("点 %d 到 %d 的最短距离是 %d\n", v, i, dist[i]);
            printf("路径为：");
            OutPutPath(i);
            printf("\n");
        }
    }
}
//划重点！！ 
void ShortestPaths()
{
    priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode> > q;   
  /*调用优先队列 ，
  第一个参数是数值类型;
  第二个参数是存放数值的容器类型，一般用vector;
  第三个参数为排序规则。 
  greater升序，即小的先出；less降序，即大的先出。
    具体函数： 
     1.插入         .push()函数
     2.取出顶端元素   .top()函数
     3.删除顶端元素   .pop()函数
     4.大小         .size()函数
     5.是否为空      .empty()函数
    */
    memset(dist, max_, sizeof(dist)); //初始化距离 
    dist[v] = 0; 
    pre[v] = v;
    MinHeapNode cur_p;
    cur_p.id = v;
    cur_p.length = 0;
    q.push(cur_p);
    while(true)
    {
        if(q.empty() == 1) //全员松弛完毕 
            break;
        cur_p = q.top(); //取出堆顶的点（距离最短） 
        q.pop(); // 在优先队列中删除刚取出的点
        for(int i = 1; i <= n; ++i)
        {
            if(Graph[cur_p.id][i] != max_ && (cur_p.length + Graph[cur_p.id][i] < dist[i]))  //剪枝函数，也就是Dijkstra中的松弛 
            {
                dist[i] = cur_p.length + Graph[cur_p.id][i];
                pre[i] = cur_p.id;
                MinHeapNode temp;
                temp.id = i;
                temp.length = dist[i];
                q.push(temp);
            }
        }
    }  
}
void InPut()   //输入数据 
{
    int x, y, len;
    scanf("%d %d %d", &v, &n, &m);  //以v为原点，n个点，m条边。 
    memset(Graph, max_, sizeof(Graph));   //默认设置为最大，表示无法到达 
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &x, &y, &len);
        Graph[x][y] = Graph[y][x] = len; //无向图！！ 
    }
}
int main()
{
    InPut();
    ShortestPaths();
    OutPut();
}