计蒜客 15969 百度地图导航 题解

题意

百度地图上有 n 个城市，城市编号依次为 1 到 n。地图中有若干个城市群，编号依次为 1 到 m。每个城市群包含一个或多个城市；每个城市可能属于多个城市群，也可能不属于任何城市群。

地图中有两类道路。第一类道路是 城市之间的快速路，两个城市 u,v 之间增加一条距离为 c 的边；第二类道路是 城市群之间的高速路，连接两个城市群 a,b，通过这条高速路，城市群 a 里的每个城市与城市群 b 里的每个城市之间两两增加一条距离为 c 的边。图中所有边均为无向边。

你需要计算从城市 s 到城市 t 的最短路。

思路

对于城市群，每个城市群拆成两个点，入和出，城市向自己所在的城市群的入点连有向边，城市群出点向城市连有向边，城市群间的边也是一个入点连接另一个出点，最后跑一遍dijkstra即可

代码

#include <cstdio> #include <vector> #include <map> #include <queue> using namespace std; #define inf 1000000000000000000LL vector<pair<long long,long long> > edge[60001]; long long dis[600001]; long long n,m,k,x,m1,u,v,c,m2,a,b,l,s,t; void dijkstra(long long v,long long *d) { long long t; priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > pq; for(long long i=1;i<=n+2*m;i++) d[i]=inf; d[v]=0; pq.push(make_pair(0,v)); while(!pq.empty()) { t=pq.top().second; pq.pop(); for(long long i=0;i<edge[t].size();i++) if(d[edge[t][i].first]>d[t]+edge[t][i].second) { d[edge[t][i].first]=d[t]+edge[t][i].second; pq.push(make_pair(d[edge[t][i].first],edge[t][i].first)); } } return; } int main() { scanf("%lld%lld",&n,&m); for(long long i=1;i<=m;i++) { scanf("%lld",&k); for(long long j=0;j<k;j++) { scanf("%lld",&x); edge[x].push_back(make_pair(n+i,0)); edge[n+m+i].push_back(make_pair(x,0)); } } scanf("%lld",&m1); for(long long i=0;i<m1;i++) { scanf("%lld%lld%lld",&u,&v,&c); edge[u].push_back(make_pair(v,c)); edge[v].push_back(make_pair(u,c)); } scanf("%lld",&m2); for(long long i=0;i<m2;i++) { scanf("%lld%lld%lld",&a,&b,&l); edge[n+a].push_back(make_pair(n+m+b,l)); edge[n+b].push_back(make_pair(n+m+a,l)); } scanf("%lld%lld",&s,&t); dijkstra(s,dis); if(dis[t]>=inf) printf("-1\n"); else printf("%lld\n",dis[t]); return 0; }