计蒜客复赛 D.百度地图导航最短路

题目链接：

https://nanti.jisuanke.com/t/15969

题意：

n个点，m个城市群，有两种边，第一种是正常的城市u与城市v之间的连边，第二种是城市群与群之间的连边，群与群之间的连边的意思是两个群之间任意两个点有一条边权为w的边。求s-t的最短路。

思路：

主要是如何处理群与群之间的连边，因为每个群最多可以2e4个点，暴力建边会T，所以我们把每个群抽象出两个点，一个点代表可以从它进入，一个点代表可以从它出去。群与群之间的边抽象成了有向边，因为这样就使得当本群里面的两个点没有边的时候，那么不能互相到达，当且仅当这个群和其他的群有第二种边，那么本群里两个点就可以相互到达，且距离是2*w，下面是官方题解：

把每个城市群抽象成两个点

对于每个城市群里面的城市

第一种边正常连边：

第二种边连边：(a',b",l),(b',a",l)

然后跑一遍 s-t

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e4+10;
17 
18 int n,m;
19 ll d[maxn*3];
20 vector<pair<int,int> > g[3*maxn];
21 
22 int main(){
23     scanf("%d%d",&n,&m);
24     for(int i=1; i<=m; i++){
25         int k = read();
26         for(int j=1; j<=k; j++){
27             int t = read();
28             g[t].push_back(MP(n+i,0));
29             g[n+m+i].push_back(MP(t,0));
30         }
31     }
32     int m1,m2,u,v,w;
33     m1 = read();
34     for(int i=1; i<=m1; i++){
35         scanf("%d%d%d",&u,&v,&w);
36         g[u].push_back(MP(v,w));
37         g[v].push_back(MP(u,w));
38     }
39     m2 = read(); int a,b;
40     for(int i=1; i<=m2; i++){
41         scanf("%d%d%d",&a,&b,&w);
42         g[a+n].push_back(MP(b+m+n,w));
43         g[b+n].push_back(MP(a+m+n,w));
44     }
45 
46     int s,t; scanf("%d%d",&s,&t);
47     for(int i=0; i<=n+2*m; i++) d[i] = INFLL;
48 
49     priority_queue<pair<ll,int> > Q;
50     d[s]=0;
51     Q.push(MP(-d[s],s));
52     while(!Q.empty()){
53         int now = Q.top().second;
54         Q.pop();
55         for(int i=0; i<(int)g[now].size(); i++){
56             int v = g[now][i].first; ll w = g[now][i].second;
57             if(d[now]+w < d[v]){
58                 d[v] = d[now]+w;
59                 Q.push(MP(-d[v],v));
60             }
61         }
62     }
63 
64     if(d[t] == INFLL) puts("-1");
65     else printf("%lld
",d[t]);
66 
67     return 0;
68 }

计蒜客复赛 D.百度地图导航 最短路

题目链接：

题意：

思路：

代码：

计蒜客复赛 D.百度地图导航最短路