HDU-1142 A Walk Through the Fores

HDU-1142 A Walk Through the Fores

题目大意：给你一个无向图，从1号点到2号点有多少种 “不绕远” 的方法

(这个“不绕远”很坑，意思是你接下来的每一步都要更接近终点，而不是寻找最短路)

要想知道下一步有没有绕远，就要知道每个点到终点的距离，这个距离一定是最短的，无向图，单源最短路，自然想到用Dijstra，扫一遍最短路，然后再用DFS去求路径个数。

Dijstra算法：从终点开始，扫一遍每一个相邻的点，把到终点的最小距离存进去，然后塞进队列或者栈里面（稍后说为什么用队列）然后从容器里面取出来一个点，标记这个点防止循环，把这个点相邻的再扫一遍，更新距离，存入容器，直到容器为空，扫过每一个点，输出起点的距离，程序结束。

分治思想，想知道起点到终点的最小距离，就要知道起点附近这一圈的点到终点的最短距离，而要知道这一圈，就要知道再下一圈，最终到达终点附近的一圈点，他们的最短就是到终点的距离。

PS：一遍过真的是谢天谢地

！！优先队列优化！！优先队列是一个有排序功能的队列，这样可以使得被取出来的元素是最小的，优先扫最短的路，超大数据情况下，可减少时间复杂度，小范围数据效果不大。

DFS：递归扫描，判断的条件是两点连通且距离更小，路径数增加的条件是寻找到终点

if(src == 2)    //搜索到终点，有一条路
{
    return 1;
}

if(way[src] != -1)      //当前点已经被搜索过一次了
{
    return way[src];
}

全部代码——>

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
 
using namespace std;
 
#define INF 0x3fffffff                          //理论上的无穷大，表示两个点不连通
#define maxn 1005
 
int load[maxn][maxn];                           //无向图，例：load[2][3] = 4;   表示点2到点3之间的距离是4;
int longload[maxn];                             //到终点的距离
bool camp[maxn];                                //标记是否已经被浏览
int way[maxn];                                  //这个点有几条路，初始化为负可同时作为标记组使用
int a,b;
 
int DFS(int src)                                //src路径起点
{
    if(way[src] != -1)      //当前点已经被搜索过一次了
    {
        return way[src];
    }
    if(src == 2)    //搜索到终点，有一条路
    {
        return 1;
    }
    way[src] = 0;       //标记
    for(int i = 1 ; i <= a ; i++)
    {
        if(longload[i] < longload[src] && load[i][src] != INF)      //下一步能走且可以走得更远
        {
            way[src] = way[src] + DFS(i);
        }
    }
    return way[src];    //搜索完成，返回结果
}
 
typedef struct node         // a 点的编号，b 到终点的距离
{
    int x , v;
    node(int a , int b)
    {
        x = a;  v = b;
    }
    friend bool operator < (node a,node b)      //友元函数，重载比较运算符，使用自定义类型的数据创建优先队列必须重载此运算符
    {
        return a.v > b.v;
    }
}creatnode;
 
int main()
{
    while(1)
    {
        int x,y,z;
        cin >> a;   if(a == 0) break;
        cin >> b;
        priority_queue<creatnode> Map;      //创建优先队列
        for(int i = 1 ; i <= a ; i++)
        {
            fill(load[i] , load[i] + maxn , INF);       //函数值替换，初始化
            camp[i] = false;                            //判定数组初始化
            longload[i] = INF;                          //存储距离
            load[i][i] = 0;
        }
        for(int i = 1 ; i <= b ; i++)           //建图
        {
            cin >> x >> y >> z;
            load[x][y] = load[y][x] = z;
        }
        longload[2] = 0;        //终点到终点距离是0
        creatnode path(2,0);
        Map.push(path);         //将起点作为第一个点入队
        //-----------------Dijkstra------------------//
        while(!Map.empty())
        {
            creatnode Q = Map.top();    Map.pop();      //取出一个点
            if(camp[Q.x] == true)   continue;           //标记
            camp[Q.x] = true;
            for(int i = 1 ; i <= a ; i++)
            {
                if(camp[i] == false && longload[i] > Q.v + load[i][Q.x])        //没有被遍历过且距离目标点的距离可以更小
                {
                    longload[i] = Q.v + load[i][Q.x];
                    creatnode path(i , longload[i]);
                    Map.push(path);                                             //符合条件，入队
                }
            }
        }
        //-------------------DFS---------------------//
        memset(way , -1 , sizeof(way));
        cout << DFS(1) << endl;
    }
    return 0;
}