分层图，建图，最短路 题意： 分析： 首先来看看我当时的思路吧！ 我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路，后是从实际生活入手的。想象一下，我们在站点i我们可以坐1,2,3三路高铁，
展开全文
根本不需要分层图，其实是dijkstra模板题 思路 让我们求从 s 到 t 的最短路关键点在于建边 有手就行 很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h>
using namespace std;
const int N = 1e3
展开全文
分层图加最短路，详情见代码蒟蒻代码，有些不清楚的地方还望谅解 //分层图 + 最短路
//https://ac.nowcoder.com/acm/contest/5338/C
//分层图在这道题上的体现就是每个集合建一个图，再在此之外建一个虚层用来进行状态的转移
//分层图的建设一般方法：有n个集合
展开全文
链接： 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format:%lld 题目描述 小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为 1∼n 。
展开全文
D、小雨坐地铁 分层建图，求单源最短路，不带负权边。如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二
展开全文
先贴代码，后挂思路
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,M=4*N;
int h[N],e[M],ne[M],w[M],idx;
int n,m,s,t,a,b,c;
int id[501][10
展开全文
题目 题目描述： 小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。 整个城市一共有 n 个车站，编号为1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi的价格。 i 号线有 ci个车站，而且这 ci个车站都已知，如果某
展开全文
题目描述小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi 的价格。i 号线有 ci 个车站，而且这 ci 个车站都已知，如果某一站有多条地铁线经过，则可以在
展开全文
思路：此题是一个分层图，需要建立把不同层次的边，我这里采用的是把站台以及每条路线上的高铁站当作节点来建立边画图，所以会有n*m+n个节点，然后就是同一条线上的节点到下一节点要b的花费，且边是无向的；然后是站台和高铁站的关系，从站台上高铁站要花费a，从高铁站下站台为0花费，建立图以后就是套模板了。
#
展开全文
题意 告诉你车站数n，地铁线路数m，起点s，终点t，然后m行描述每一条地铁的上车价格a，每坐一站价格b，车站数c，以及c个车站号，求最小花费。 题解 显然，是一个很裸的最短路。但是直接以站点为节点，地铁线路作为边是不能简单的用Dij过的，毕竟贪心算法，直接这么莽会wa的（我还真试过，wa了，自己也找
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
