178. 第K短路（bfs）

迷南。 2021-11-11 04:56 200阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/180/][https_www.acwing.com_problem_content_description_180]  
给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。  
输入格式

第一行包含两个整数N和M。

接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。

最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。  
输出格式

输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。  
数据范围

1≤S,T≤N≤1000  
,  
0≤M≤105,  
1≤K≤1000,  
1≤L≤100

输入样例：

2 2  
1 2 5  
2 1 4  
1 2 2

输出样例：

分析：  
怎么会有我这么蠢的人呀。同时，怎么会有这样水的数据呀。  
好吧，认真分析一波。  
A*算法  
A*算法核心思想就是预估接下来的情况，达到优先搜索整体最优的目的，以减少搜索层次。  
简单的说，就是我们平常用优先队列求最短路的时候，就是拿当前最少的距离来拓展，现在就要考虑一下他之后的情况，在拓展了。

1，我们可以预处理一下以T为起点到其他点的最短路径（注意，这是个有向图。现在是求T到其他的点，那么我们需要新建一个和给定图相反方向的图。555 一开始竟然没考虑到）。  
2，优先队列，不过里面考虑比较的值为实际距离长度+预估长度。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"queue"
    #include"algorithm"
    using namespace std;
    typedef pair<int,int> PII;
    #define INF 100101010
    
    typedef struct Node
    {
        int u,real,f;
        friend bool operator < (Node a,Node b)
        {
            return a.f > b.f;
        }
        Node(){}
        Node(int a,int b,int c)
        {
            u = a; real = b; f = c;
        }
    }Node;
    
    int num_cnt[1010];
    int dist_min[1010];
    vector<PII> Graph[1010];
    vector<PII> G[1010];
    int S,T,N,M,K;
    int minx_K;
    
    struct cmp
    {
        bool operator()(const PII p1,const PII p2)
        {
            return p1.second > p2.second;
        }
    };
    void bfs_min()
    {
        priority_queue<PII,vector<PII>,cmp > Q;
        Q.push({T,0});
        int vis[1010];
        memset(vis,0,sizeof(vis));
        dist_min[T] = 0;
        while(!Q.empty())
        {
            PII T = Q.top();
            Q.pop();
            if(vis[T.first] == 0)
            {
                for(int i = 0; i < G[T.first].size(); i ++)
                {
                    PII t = G[T.first][i];
                    if(dist_min[t.first] > dist_min[T.first] + t.second)
                    {
                        dist_min[t.first] = dist_min[T.first] + t.second;
                        Q.push({t.first, dist_min[t.first]});
                    }
                }
                vis[T.first] = 1;
            }
        }
    }
    
    int bfs_k()
    {
        priority_queue<Node> Q;
        Q.push({S,0,0 + dist_min[S]});
        while(!Q.empty())
        {
            Node A = Q.top(); Q.pop();
            num_cnt[A.u] ++;
            if(num_cnt[A.u] == K && A.u == T)
            {
                minx_K = A.real; return 1;
            }
            for(int i = 0; i < Graph[A.u].size(); i ++)
            {
                PII X = Graph[A.u][i];
               // if(num_cnt[X.first] > K) continue;
                Q.push({X.first,A.real + X.second,A.real + X.second + dist_min[X.first]});
            }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
        for(int i = 0; i <= N; i ++) dist_min[i] = INF;
        for(int i = 1; i <= M; i ++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            Graph[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        scanf("%d%d%d",&S,&T,&K);
        if(S == T) K ++;
        bfs_min();
    
        if(dist_min[S] == INF || M == 0)
        {
            printf("-1\n"); return 0;
        }
        if(bfs_k() == 1)
        printf("%d\n",minx_K);
        else
        printf("-1\n");
    }

[https_www.acwing.com_problem_content_description_180]: https://www.acwing.com/problem/content/description/180/