牛客国庆集训派对Day3 I. - Metropolis (Dijkstra变型)

题意:求一个N个点无向图中,其中p个关键点间的最短距离.

分析:比较特殊的最短路,方式类似于多源BFS,将所有关键点装入优先队列,状态中需要包含其源点的id.对每条边都要遍历,对每个节点,需要记录其确定最短的源头以及其最短距离.当一个访问状态到达了与自己源头状态不同的点,则说明两个关键点相遇,每次相遇时,更新两个源头的最短距离.

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+5;

const LL INF = (1LL)<<60;

struct Edge{

    int v,next;

    LL w;

}E[MAXN<<2];

int head[MAXN],tot;

int vis[MAXN];

LL d[MAXN],link[MAXN];

vector<int> st;

int N,M,k;

void init()

{

    st.clear();

    memset(head,-1,sizeof(head));

    tot = 0;

}

void AddEdge(int u,int v,int w){

    E[tot] = (Edge){v,head[u],w};

    head[u] = tot++;

}

struct HeapNode{

    int u,sta;

    LL val;

    bool operator < (const HeapNode & rhs) const{

        return val > rhs.val;

    }

};

void Dijkstra()

{

    for(int i=0;i<=N;++i)   d[i] = INF, vis[i] = 0;

    priority_queue<HeapNode> Q;

    for(int i=0,sz = st.size();i<sz;++i){

        int u = st[i];

        d[u] = 0;

        link[u] = INF;

        Q.push((HeapNode){u,u,0});

    }

    while(!Q.empty()){

        HeapNode x = Q.top(); Q.pop();

        int u = x.u, sta = x.sta;

        if(vis[u] == 0){

            vis[u] = sta;

            d[u] = x.val;

            for(int i=head[u]; ~i; i = E[i].next){

                int v = E[i].v;

                Q.push((HeapNode){v,sta,d[u]+E[i].w});

            }

        }

        else if(vis[u] != sta){

            int fu = vis[u];

            link[sta] = min(link[sta], x.val + d[u]);

            link[fu] = min(link[fu], x.val+ d[u]);

        }

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    scanf("%d %d %d",&N, &M, &k);

    init();

    int u,v;

    LL w;

    while(k--){

        scanf("%d",&u);

        st.push_back(u);

    }

    while(M--){

        scanf("%d %d %lld",&u,&v,&w);

        AddEdge(u,v,w);

        AddEdge(v,u,w);

    }

    Dijkstra();

    for(int i=0,sz = st.size();i<sz;++i){

        printf("%lld%c",link[st[i]], i==sz-1?'\n':' ');

    }

    return 0;

}

巴特西

牛客国庆集训派对Day3 I. - Metropolis (Dijkstra变型)

最新文章

热门文章