首页 > 试题广场 >

小雨坐地铁

[编程题]小雨坐地铁

热度指数：3 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

小雨所在的城市一共有 $m$ 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 $n$ 个车站，编号为 $1 \sim n$ 。其中坐 i 号线需要花费 $a_i$ 的价格，每坐一站就需要多花费 $b_i$ 的价格。i 号线有 $c_i$ 个车站，而且这 $c_i$ 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 $s$ 个车站坐地铁到第 $t$ 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 $s$ 可能大于 $t$ ）

输入描述:

第一行输入四个正整数 ，分别表示车站个数，地铁线数，起点站和终点站。
第二行到第  行，每行前三个数为 ，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来  个数，表示 i 号线的每一个车站的编号，单调递增。

输出描述:

共一行，一个数表示最小花费，若不能到达输出 -1 。

示例1

输入

5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5

输出

说明

坐 1 号线：花费 2；

：花费 2；

换乘 2 号线：花费 2；

：花费 1；

所以最小总花费为 7 。

备注:

算法知识视频讲解

苟且的狮子

发表于 2020-07-27 22:44:45

分层图，建图，最短路题意：分析：首先来看看我当时的思路吧！我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路，后是从实际生活入手的。想象一下，我们在站点i我们可以坐1,2,3三路高铁，展开全文

sunny_forever

发表于 2021-07-09 15:09:33

根本不需要分层图，其实是dijkstra模板题思路让我们求从 s 到 t 的最短路关键点在于建边有手就行很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h> using namespace std; const int N = 1e3 展开全文

lyting2001

发表于 2020-04-21 21:54:57

分层图加最短路，详情见代码蒟蒻代码，有些不清楚的地方还望谅解 //分层图 + 最短路 //https://ac.nowcoder.com/acm/contest/5338/C //分层图在这道题上的体现就是每个集合建一个图，再在此之外建一个虚层用来进行状态的转移 //分层图的建设一般方法：有n个集合展开全文

回归梦想

发表于 2020-04-26 20:55:05

链接：时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format:%lld 题目描述小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为 1∼n 。展开全文

sunrise__sunrise

发表于 2020-05-06 10:00:58

D、小雨坐地铁分层建图，求单源最短路，不带负权边。如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二展开全文

huyaowen

发表于 2022-05-02 19:06:35

先贴代码，后挂思路 #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 展开全文

19_hanhan

发表于 2020-05-08 00:27:17

题目题目描述：小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n 个车站，编号为1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi的价格。 i 号线有 ci个车站，而且这 ci个车站都已知，如果某展开全文

JQK2020

发表于 2020-06-30 19:21:22

题目描述小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi 的价格。i 号线有 ci 个车站，而且这 ci 个车站都已知，如果某一站有多条地铁线经过，则可以在展开全文

nanfengjiuchui

发表于 2023-08-10 20:43:58

思路：此题是一个分层图，需要建立把不同层次的边，我这里采用的是把站台以及每条路线上的高铁站当作节点来建立边画图，所以会有n*m+n个节点，然后就是同一条线上的节点到下一节点要b的花费，且边是无向的；然后是站台和高铁站的关系，从站台上高铁站要花费a，从高铁站下站台为0花费，建立图以后就是套模板了。 # 展开全文

VoidJackLee

发表于 2020-05-06 22:20:08

题意告诉你车站数n，地铁线路数m，起点s，终点t，然后m行描述每一条地铁的上车价格a，每坐一站价格b，车站数c，以及c个车站号，求最小花费。题解显然，是一个很裸的最短路。但是直接以站点为节点，地铁线路作为边是不能简单的用Dij过的，毕竟贪心算法，直接这么莽会wa的（我还真试过，wa了，自己也找展开全文