ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[JLOI2011]飞行路线(dijkstra分层最短路)

2022年3月6日 1087点热度 0人点赞 0条评论

题目链接:K-[JLOI2011]飞行路线_WUT2021校内训练⑦ (nowcoder.com)

题意请看原题,是中文的。

思路

本题突破口在K <= 10,且N <= 1e4。

设起点s, 终点t。

一般的最短路的题目都是建立一个二维图,这里我们建立一个K层的三维图,从第 0 层开始,第 i 层表示用了 i 次免费航线。这样最后统计所有t + N * i(0 <= i <= K)的点到源点的距离的最小值即可。

建图使用了一维拓展的方式,[0, N - 1]表示第一层,[N, 2 * N - 1]表示第二层,以此类推。

需要注意的是,建图的时候,需要给每一层的二维图都建立起边,并且将相邻的两层之间建立权值为0的免费航线。具体实现方法看代码。

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define pb push_back
#define sc scanf
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
     int s = 0,w = 1;char c = gc();
     while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
     while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
     return s * w;
}
/*--------全局变量--------*/
const int maxn = 1e5 + 2e4 + 10,inf = 1e15;
int N, M, K, s, t;

struct Node
{
     int x, d;
     bool operator < (const Node &m)const{return d > m.d;}
};
vector<Node> g[maxn];
int dist[maxn];
/*--------自定义函数-------*/

inline bool dijkstra(int s,int t)
{
     memset(dist, 127, sizeof dist);
     priority_queue<Node> pq;
     pq.push({s, 0});
     while(!pq.empty())
     {
          int x = pq.top().x;
          int d = pq.top().d;
          pq.pop();
          if(x == t)return 1;
          if(d > dist[x])continue;
          for(auto i : g[x])
               if(d + i.d < dist[i.x])pq.push({i.x, dist[i.x] = d + i.d});
     }
     return 0;
}

signed main()
{
     N = readInt(), M = readInt(), K = readInt();
     s = readInt(), t = readInt();
     while(M --)
     {
          int x = readInt(), y = readInt(), w = readInt();
          for(int i = 0;i <= K; ++ i)
          {
               g[x + N * i].pb({y + N * (i + 1), 0});
               g[y + N * i].pb({x + N * (i + 1), 0});
               g[x + N * i].pb({y + N * i, w});
               g[y + N * i].pb({x + N * i, w});
          }
     }
     dijkstra(s, t);
     int ans = inf;
     for(int i = 0;i <= K; ++ i)ans = min(ans, dist[t + N * i]);
     pr("%lld\n",ans);
     return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ dijkstra 最短路 牛客网
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 思路
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号