也是第一次接触这种分层建图的最短路
思路:由题目我们可以知道某些站点是可以连接好几条地铁线路的,那么对于每条地铁线路我们可以把他当成一幅图来算。当然图是个无向图,所以要加两次边。
add(i*n+x,i*n+pre,b); //乘i的话就是说把他建在第i层,这个pre是记录上一个点的位置。
add(i*n+pre,i*n+x,b);
处理换乘时的操作
利用到我们刚刚所说的虚点
add(x,i*n+x,a); //从虚点到地铁线上需要花费,花费坐这条线的价格//也就是题中(坐i号线需要花费a[i]的价格)
add(i*n+x,x,0); //从地铁线上到虚点花费为0
根据题目中样例建成的图就是(有点丑,别介意)
接下来的过程就跟最短路模板题一样了
代码:
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
struct wazxy{int to,w,next;
}edge[maxn];
struct node{int n,dis;node(int a,int b){n=a,dis=b;}bool operator <(const node & a)const{return dis>a.dis;}
};
int dis[maxn];
int head[maxn];
int cnt=0,n,m,s,t;
bool visited[maxn];
void init(){memset(head,-1,sizeof(head));memset(visited,false,sizeof(visited));memset(dis,MaxN,sizeof(dis));
}
void add(int u,int v,int w){edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
}
void dij(int x){dis[x]=0;priority_queue<node> q;q.push(node(x,0));while(!q.empty()){node temp=q.top();q.pop();if(visited[temp.n]) continue;visited[temp.n]=true;for(int i=head[temp.n];~i;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(visited[v]) continue;if(dis[v]>temp.dis+w){dis[v]=temp.dis+w;q.push(node(v,dis[v]));}}}
}
int main()
{cin>>n>>m>>s>>t;init();for(int i=1;i<=m;i++){int a,b,c,x;scanf("%d%d%d",&a,&b,&c);int pre=-1;while(c--){cin>>x;if(pre!=-1){add(i*n+x,i*n+pre,b); //乘i的话就是说把他建在第i层add(i*n+pre,i*n+x,b);}add(x,i*n+x,a);add(i*n+x,x,0);pre=x;}}dij(s);if(dis[t]==MaxN) cout<<"-1"<<endl;else cout<<dis[t]<<endl;return 0;
}