分层图加最短路,详情见代码
蒟蒻代码,有些不清楚的地方还望谅解
//分层图 + 最短路
//https://ac.nowcoder.com/acm/contest/5338/C
//分层图在这道题上的体现就是每个集合建一个图,再在此之外建一个虚层用来进行状态的转移
//分层图的建设一般方法:有n个集合,任意一个集合最多有m个元素。
//先开一个大小为n * m的数组a[N * M]。
//对任意一个集合i来说,其中任意第x个元素存储在a[(i - 1) * m + x]中
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 7;
const int M = 510;
const int maxn = N * M;
const int INF = 0x3f3f3f3f;
int e[maxn], ne[maxn], w[maxn], h[maxn], idx; //因为是稀疏图,我们就用领接表做
int n, m, s, t;
int dis[maxn]; //存储最短距离
bool vis[maxn]; //存储这个点有没有被访问过
void add(int a, int b, int c) //模板不多说,w[N]为权重,为两点之间的距离
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void dijkstra(int s) //堆优化的Dijkstra
{
memset(dis, INF, sizeof dis);
dis[s] = 0;
priority_queue<PII, vector<PII>, greater<PII> > heap; //声明一个优先队列,本质上是个小根堆
heap.push({0, s}); //把第一个点加入堆中,pair的话优先按照first的大小排,所以必须写{0,1},不能写{1,0}
while(!heap.empty())
{
auto t = heap.top(); //取出队列中的第一个数,取出后删掉
heap.pop();
int ver = t.second;
if(vis[ver])
continue;
else
vis[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]) //遍历所有出点
{
int x = e[i];
if(dis[x] > dis[ver] + w[i])
{
dis[x] = dis[ver] + w[i];
heap.push({dis[x], x});
}
}
}
}
int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++)
{
int a, b, c, pre; //这里的pre是上一层x的拷贝,方便下一次把点连起来
cin >> a >> b >> c;
for(int j = 1; j <= c; j++)
{
int x;
cin >> x;
add((i - 1) * n + x, n * m + x, 0); //这里的n * m是虚层,点到虚层的代价是0,虚层到点的代价就是转线的代价
add(n * m + x, (i - 1) * n + x, a); //这里我们把点连到虚层,再从虚层把点连回来
if(j != 1)
{
add((i - 1) * n + pre, (i - 1) * n + x, b); //这里连接相邻的两个站
add((i - 1) * n + x, (i - 1) * n + pre, b);
}
pre = x;
}
}
dijkstra(n * m + s);
if(dis[n * m + t] == INF)
cout << -1 << endl;
else
cout << dis[n * m + t];
return 0;
}
京公网安备 11010502036488号