LOJ6354 & 洛谷4366：[Code+#4]最短路—

https://loj.ac/problem/6354

https://www.luogu.org/problemnew/show/P4366

题面见上面。

这题很妙，且可能是我傻，感觉这题不太好想。

前45pts很好骗就不说了。

朴素的建法是O(n^2+m)的，一个点都过不了。

然而事实上一个从x->y权值为w的边是可以被其他边取代的，我们可以把x拆成二进制，一位一位的修改最终到达y，此时经过的权值显然也是w。

也就是说，对于一个点x，我们只需要让他和x*2^k连边即可，这样就优化为O(nlogn+m)了，跑一遍dij就好了。

另外这题将我的dij卡T了于是去抄了别人的dij难受啊啊orz。

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef pair<int,int>pii;

#define fi first

#define se second

const int N=1e5+;

const int M=5e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt,w;

}e[M+N*];

int n,m,c,cnt,head[N];

inline void add(int u,int v,int w){

    e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;

}

int dis[N];

priority_queue<pii,vector<pii>,greater<pii> >q;

void dij(int s){

    memset(dis,,sizeof(dis));

    dis[s]=;q.push(pii(,s));

    while(!q.empty()){

    int u=q.top().se,f=q.top().fi;q.pop();

    if(f!=dis[u])continue;

    for(int i=head[u];i;i=e[i].nxt){

        int v=e[i].to,w=e[i].w;

        if(dis[v]>dis[u]+w){

        dis[v]=dis[u]+w;

        q.push(pii(dis[v],v));

        }

    }

    }

    return;

}

int main(){

    n=read(),m=read(),c=read();

    for(int i=;i<=m;i++){

    int u=read(),v=read(),w=read();

    add(u,v,w);

    }

    for(int u=;u<=n;u++){

    for(int i=;i<=n;i<<=){

        int v=u^i;if(v>n)continue;

        add(u,v,i*c);

    }

    }

    int s=read(),t=read();

    dij(s);

    printf("%d\n",dis[t]);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

巴特西

LOJ6354 & 洛谷4366：[Code+#4]最短路——题解

最新文章

热门文章