P4568 飞行路线【分层图最短路】

题目链接：https://www.luogu.org/problem/P4568

题目大意：给定n个点，m条无向边，k次机会经过边时代价为 0 。给出起点和终点，求其最短路径。

解题思路：

两种方法，一是用拆点分层，直接跑最短路。二是dis[][]开二维数组，表示已经用了 j 次免费机会时在 i 点的最短路径。

第一种方法数组需要多开大很多倍（因为拆点），当层数以及点比较多的时候，边也就非常多，代码跑起来很慢，在这里若不用优先队列dijsktra优化会超时。

第二种方法似乎更加好，不需要将一维数组开大很多倍，只需要用二维数组记录状态，然后更新即可。跑的边也会比较的少。代码更快。

对于第一种方法。图如下：

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 #include<algorithm>

 #define mem(a, b) memset(a, b, sizeof(a))

 typedef long long ll;

 const int MAXN = 1e6 + ;//建了多层 点成倍增加

 const int MAXM = 5e6 + ;

 const int inf = 0x3f3f3f3f;

 using namespace std;

 int n, m, k, st, ed;

 int head[MAXN], cnt;

 int vis[MAXN];

 ll dis[MAXN];  //距离开ll 稳 

 struct Edge

 {

     int to, next;

     ll w;

 }edge[MAXM];

 struct Node

 {

     int pot;

     ll dis;

     bool operator < (const Node &a)const

     {

         return dis > a.dis;

     }

 }node;

 void add(int a, int b, ll c)

 {

     cnt ++;

     edge[cnt].to = b;

     edge[cnt].w = c;

     edge[cnt].next = head[a];

     head[a] = cnt;

 }

 void dij()

 {

     mem(dis, inf), mem(vis, );

     priority_queue<Node> Q; //记得是优先队列

     while(!Q.empty())    Q.pop();

     dis[st] = ;

     node.pot = st, node.dis = ;

     Q.push(node);

     while(!Q.empty())

     {

         Node a = Q.top();//top()

         Q.pop();

         if(vis[a.pot])

             continue;

         vis[a.pot] = ;

         for(int i = head[a.pot]; i != -; i = edge[i].next)

         {

             int to = edge[i].to;

             if(vis[to]) //若该点以及确定了最短距离 则不需要再去比较了

                 continue;

             if(dis[to] > dis[a.pot] + edge[i].w)

             {

                 dis[to] = dis[a.pot] + edge[i].w;

                 node.pot = to, node.dis = dis[to];

                 Q.push(node);

             }

         }

     }

 }

 int main()

 {

     cnt = , mem(head, -);

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

     scanf("%d%d", &st, &ed);

     for(int i = ; i <= m; i ++)

     {

         int a, b;

         ll c;

         scanf("%d%d%lld", &a, &b, &c);

         add(a, b, c);

         add(b, a, c);

         for(int j = ; j <= k; j ++)

         {

             add(a + (j - ) * n, b + j * n, );  //上一层往下一层建边权为 0 的边

             add(b + (j - ) * n, a + j * n, );

             add(a + j * n, b + j * n, c);  //每一层本身的边也要建

             add(b + j * n, a + j * n, c);

         }

     }

     dij();

     ll ans = inf;

     for(int i = ; i <= k; i ++)  //选择到终点距离最短的那一层答案

         ans = min(ans, dis[ed + i * n]);

     printf("%lld\n", ans);

     return ;

 }

建图时分层

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 #define mem(a, b) memset(a, b, sizeof(a))

 typedef long long ll;

 const int MAXN = 1e4 + ;

 const int MAXM = 5e4 + ;

 const int inf = 0x3f3f3f3f;

 using namespace std;

 int n, m, k, st, ed;

 int head[MAXN], cnt, vis[MAXN][];

 ll dis[MAXN][];

 struct Edge

 {

     int to, next;

     ll w;

 }edge[ * MAXM];

 struct Node

 {

     int pot, num;  //点 以及 用了的机会次数

     ll dis;

     bool operator < (const Node &a)const

     {

         return dis > a.dis;

     }

 }node;

 void add(int a, int b, ll c)

 {

     cnt ++;

     edge[cnt].w = c;

     edge[cnt].to = b;

     edge[cnt].next = head[a];

     head[a] = cnt;

 }

 void dij()

 {

     mem(dis, inf), mem(vis, );

     node.pot = st, node.dis = , node.num = ;

     dis[st][] = ;

     priority_queue<Node> Q;

     Q.push(node);

     while(!Q.empty())

     {

         Node a = Q.top();

         Q.pop();

         if(vis[a.pot][a.num])

             continue;

         vis[a.pot][a.num] = ;

         for(int i = head[a.pot]; i != -; i = edge[i].next)

         {

             int to = edge[i].to;

             if(dis[to][a.num] > dis[a.pot][a.num] + edge[i].w) //不使用免费机会

             {

                 dis[to][a.num] = dis[a.pot][a.num] + edge[i].w;

                 node.pot = to, node.dis = dis[to][a.num], node.num = a.num;

                 Q.push(node);

             }

             if(a.num == k)   //如果已经把免费机会使用完了

                 continue;

             if(dis[to][a.num + ] > dis[a.pot][a.num])

             {

                 dis[to][a.num + ] = dis[a.pot][a.num];

                 node.pot = to, node.dis = dis[to][a.num + ], node.num = a.num + ;

                 Q.push(node);

             }

         }

     }

 }

 int main()

 {

     mem(head, -), cnt = ;

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

     scanf("%d%d", &st, &ed);

     for(int i = ; i <= m; i ++)

     {

         int a, b;

         ll c;

         scanf("%d%d%lld", &a, &b, &c);

         add(a, b, c);

         add(b, a, c);

     }

     dij();

     ll ans = inf;

     for(int i = ; i <= k; i ++)

         ans = min(ans, dis[ed][i]);

     printf("%lld\n", ans);

     return ;

 }

二维数组

巴特西

P4568 飞行路线【分层图最短路】

最新文章

热门文章