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+5; const int M=5e5+5; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } struct node{int to,nxt,w; }e[M+N*20]; 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,127,sizeof(dis));dis[s]=0;q.push(pii(0,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=1;i<=m;i++){int u=read(),v=read(),w=read();add(u,v,w);}for(int u=0;u<=n;u++){for(int i=1;i<=n;i<<=1){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 0; }

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

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/?+

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

轉載于:https://www.cnblogs.com/luyouqi233/p/9059940.html

總結

以上是生活随笔為你收集整理的LOJ6354 洛谷4366：[Code+#4]最短路——题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。