分层图加最短路,详情见代码
蒟蒻代码,有些不清楚的地方还望谅解
//分层图 + 最短路 //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; }