小雨坐地铁 (分层最短路&建立虚点)
思路:建立一个虚点层,题目等价于求虚点层起点到终点的最小花费。同一层边花费b,虚点层到其他每层花费a。跑一边dijkstra即可。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,inf=0x3f3f3f3f;
struct edge{
int to,nt,w;
}e[N];
int h[N],n,m,d[N],cnt=1,st,ed,vis[N];
struct node{
int d,id;
bool operator<(const node&a)const{
return d>a.d;
}
};
void add(int u,int v,int w){
e[cnt]={v,h[u],w};
h[u]=cnt++;
}
void dij(){//dijstra板子
priority_queue<node>q;
memset(d,0x3f,sizeof d);
d[st]=0;
q.push({d[st],st});
while(q.size()){
int u=q.top().id;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to,w=e[i].w;
if(!vis[v]&&d[v]>d[u]+w)
d[v]=d[u]+w,q.push({d[v],v});
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);st=n*m+st,ed=n*m+ed;//从虚点层的起点到终点的花费即为答案.
for(int i=0;i<m;i++)
{
int a,b,c,u,v;
scanf("%d%d%d",&a,&b,&c);
for(int j=0;j<c;j++)
{
scanf("%d",&u);
if(j) add(u+i*n,v+i*n,b),add(v+i*n,u+i*n,b);//同层连边.
add(u+i*n,u+m*n,0),add(u+m*n,u+i*n,a);//每一层都连向虚点不用花费,虚点到其他层需要花费a
v=u;
}
}
dij();
printf(d[ed]==inf?"-1\n":"%d\n",d[ed]);
return 0;
}