计蒜之道 2017 程序设计大赛 - 计蒜客复赛 D 百度地图导航最短路、Dijkstra的拓展

Source

计蒜之道 2017 程序设计大赛 - 计蒜客复赛 D 百度地图导航

计蒜客 15969 百度地图导航

My Solution

题意：有 n 个点，编号依次为 1 到 n，且有若干个点的集合，编号依次为 1 到 m。每个点集合包含一个或多个点；每个点可能属于多个点集合，也可能不属于任何点集合。

图中中有两种边。第一类边是点u,v 之间权值为ci的无向边；第二类边是点集合之间的无向边，连接两个点集合 a,b，通过这条边，城市群 a 里的每个点与点集合 b 里的每个点之间有一条权值为 w 的无向边。求从点s 到点 t 的最短路。

最短路、Dijkstra的拓展

这里n+m是4e4所以很可能只能用O(nlogn)的算法，所以可以用Dijkstra+堆优化来进行拓展，

这里把点集合 a作为点 a+n来进行存储，然后dis[i]表示当前从起点s到点或者点集合i的最短路权值。

然后建立这个点集合到点的映射 vector from[a], 和点到它所在的集合的映射 vector to[u]。

然后跑Dijkstra的时候，如果从小根堆取出的点是表示普通的点则和普通的Dijkstra一样跑，

然后对于这个点映射出的点集合也跑一边松弛操作，

szto = to[u].size();
for(j = 0; j < szto; j++){
sz = sons[to[u][j]].size();
uu = to[u][j];
for(i = 0; i < sz; i++){
v = sons[uu][i].first;
w = sons[uu][i].second;
if(d + w < dis[v]){
dis[v] = d + w;
pq.push(ii(dis[v], v));
}
}
}

如果 u>n则表示这是一个点集合，在进行常规松弛操作之后，还要把dis[u]更新到所有的点集合u映射到的点，

sz = from[u].size();
for(i = 0; i < sz; i++){
v = from[u][i];
if(d < dis[v]){
dis[v] = d;
pq.push(ii(dis[v], v));
}
}

跑完Dijkstra后答案就是dis[destination]了。

时间复杂度 O((n+m)log(n+m))

空间复杂度 O(N)

#include 
#include 
#include 
#include 

#include 
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
const int MAXN = 4e4 + 8;
const LL INF = 9e18 + 8;

vector to[MAXN], from[MAXN];

vector sons[MAXN];
LL dis[MAXN];
bool vis[MAXN];
priority_queue<ii, vector, greater > pq;
//O(nlogn)
inline void dijkstra(int n, int src)
{
    for(int i = 1; i <= n; i++){
        dis[i] = INF;
    }
    memset(vis, false, sizeof vis);
    dis[src] = 0;
	while(!pq.empty()) pq.pop();
	pq.push(ii(0, src));
	LL u, v, w, d, sz, i, j, szto, uu;
	while(!pq.empty()){

        u = pq.top().second;
        d = pq.top().first;//cout << u << " " << d << endl;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        //
        sz = sons[u].size();
		for(i = 0; i < sz; i++){
			v = sons[u][i].first;
			w = sons[u][i].second;
			if(d + w < dis[v]){
				dis[v] = d + w;
				pq.push(ii(dis[v], v));
			}
		}
		//
		szto = to[u].size();
		for(j = 0; j < szto; j++){
            sz = sons[to[u][j]].size();
            uu = to[u][j];
            for(i = 0; i < sz; i++){
                v = sons[uu][i].first;
                w = sons[uu][i].second;
                if(d + w < dis[v]){
                    dis[v] = d + w;
                    pq.push(ii(dis[v], v));
                }
            }
		}
		//
		sz = from[u].size();
		for(i = 0; i < sz; i++){
            v = from[u][i];
            if(d < dis[v]){ dis[v] = d; pq.push(ii(dis[v], v)); } } } } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.txt", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, m, k, i, j, m1, m2, src, dest, e, u, v, w, ans = INF; cin >> n >> m;
    for(i = 1; i <= m; i++){ cin >> k;
        for(j = 0; j < k; j++){ cin >> u;
            to[u].push_back(i+n);
            from[i+n].push_back(u);
        }
    }
    cin >> m1;
    while(m1 && m1--){
        cin >> u >> v >> w;
        sons[u].push_back(ii(v, w));
        sons[v].push_back(ii(u, w));
    }
    cin >> m2;
    while(m2 && m2--){
        cin >> u >> v >> w;
        sons[u+n].push_back(ii(v+n, w));
        sons[v+n].push_back(ii(u+n, w));
    }

    cin >> src >> dest;

    dijkstra(n+m, src);
    ans = dis[dest];
    /*
    int sz = to[dest].size(), szfrom, uu;
    for(i = 0; i < sz; i++){
        uu = to[dest][i];
        szfrom = from[uu].size();
        for(j = 0; j < szfrom; j++){
            ans = min(ans, dis[from[uu][j]]);
        }
    }
    */

    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

计蒜之道 2017 程序设计大赛 – 计蒜客复赛 D 百度地图导航最短路、Dijkstra的拓展