1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| void connect(vector<vector<pair<int,int>>>& adj, vector<vector<int>>& E) {
for(int i = 0; i < E.size(); i++) {
int u = E[i][0], v = E[i][1], c = E[i][2];
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
}
int Solution::solve(int A, vector<vector<int> > &B, int C, int D, vector<vector<int> > &E) {
vector<vector<pair<int, int>>> adj(101010);
vector<vector<pair<int, int>>> adj2(101010);
connect(adj,B);
connect(adj2,E);
priority_queue<array<int,3>,vector<array<int,3>>, greater<array<int,3>>> q;
vector<vector<int>> vis(2,vector<int>(101010, INT_MAX));
q.push({0,C,0});
vis[0][C] = 0;
while(!q.empty()) {
auto [c, u, fl] = q.top(); q.pop();
if(vis[fl][u] != c) continue;
for(auto& [v, w] : adj[u]) {
if(vis[fl][v] < c + w) continue;
vis[fl][v] = c + w;
q.push({c+w,v,fl});
}
if(!fl) {
for(auto& [v, w] : adj2[u]) {
if(vis[1][v] < c + w) continue;
vis[1][v] = c + w;
q.push({c+w,v,1});
}
}
}
return min(vis[0][D], vis[1][D]) == INT_MAX ? -1 : min(vis[0][D], vis[1][D]);
}
|
