BZOJ 2763 飞行路线 BFS分层

时间：2021-11-26 11:09:07

题目链接：

https://www.lydsy.com/JudgeOnline/problem.php?id=2763

题目大意：

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

思路：

BFS分层即可。

 #include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #define MID(l, r) ((l) + ((r) - (l)) / 2)

 #define lson ((o)<<1)

 #define rson ((o)<<1|1)

 #define Accepted 0

 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn =  + ;

 const int MOD = ;//const引用更快，宏定义也更快

 const int INF = 1e9 + ;

 const double eps = 1e-;

 bool vis[maxn][];

 struct edge

 {

     int v, w;

     edge(){}

     edge(int v, int w):v(v), w(w){}

 };

 vector<edge>G[maxn];

 int n, m, k;

 int s, t;

 struct Heapnode

 {

     int d, id, k;//距离 点 层数

     Heapnode(){}

     Heapnode(int d, int id, int k):d(d), id(id), k(k){}

     bool operator< (const Heapnode & a)const

     {

         return d > a.d || d == a.d && k > a.k;

     }

 };

 priority_queue<Heapnode>q;

 int BFS()

 {

     q.push(Heapnode(, s, ));

     while(!q.empty())

     {

         Heapnode now = q.top();

         q.pop();

         if(vis[now.id][now.k])continue;

         vis[now.id][now.k] = ;

         if(now.id == t)

         {

             return now.d;

         }

         for(int i = ; i < G[now.id].size(); i++)

         {

             int v = G[now.id][i].v;

             int w = G[now.id][i].w;

             if(!vis[v][now.k])

             {

                 q.push(Heapnode(now.d + w, v, now.k));

             }

             if(!vis[v][now.k + ] && now.k +  <= k)

             {

                 q.push(Heapnode(now.d, v, now.k + ));

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d%d", &n, &m, &k);

     scanf("%d%d", &s, &t);

     while(m--)

     {

         int u, v, w;

         scanf("%d%d%d", &u, &v, &w);

         G[u].push_back(edge(v, w));

         G[v].push_back(edge(u, w));

     }

     printf("%d\n", BFS());

     return Accepted;

 }

相关文章