NC26257 小雨坐地铁
题意：
有n个点，m条地铁线，每条地铁线有一个三个值，分别表示这条地铁线上车的费用，坐一站的费用，和这条地铁线包含几个点，现在你需要从第 s 个地铁站到达第 t 个地铁站，问你至少需要花费多少钱？
做法：
和之前两个题目一样的做法，分层图最短路，不过这里的代码实现采用建虚点的方式，也就是说，对于每个点，我们将他在m个地铁线上的时候看作不一样的点，并且额外定义一个虚点表示下车，从m个地铁线上的点走到对应的虚点表示下车，不需要花钱，反之，表示上车，需要花费对应地铁线的上车费，建图完成之后直接跑最短路即可得到最小花费。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 6e5;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
struct edge
{
int to;
ll w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
ll dis[MAXN];
bool vis[MAXN];
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
for (int i = 0; i < MAXN; i++)
dis[i] = inf;
}
void add(int a, int b, ll c)
{
e[tot] = edge{ b,c,head[a] };
head[a] = tot++;
}
#define Pair pair<int,int>
void dij(int s)
{
priority_queue<Pair, vector<Pair>, greater<Pair> >q;
q.push(Pair{ 0,s });
dis[s] = 0;
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
q.push(Pair{ dis[v],v });
}
}
}
}
int n, m, s, t;
int in[1005];
int main()
{
init();
scanf("%d%d%d%d", &n, &m, &s, &t);
int a, b, cnt;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &cnt);
for (int j = 0; j < cnt; j++)
{
scanf("%d", &in[j]);
if (j > 0)
{
add(i * n + in[j - 1], i * n + in[j], b);
add(i * n + in[j], i * n + in[j - 1], b);
}
add(i * n + in[j], m * n + in[j], 0);
add(m * n + in[j], i * n + in[j], a);
}
}
dij(m * n + s);
if (dis[m * n + t] == inf)
dis[m * n + t] = -1;
printf("%lld\n", dis[m * n + t]);
} 
小米开奖105人在聊
投递字节跳动等公司10个岗位 >