正題

題目鏈接:https://darkbzoj.tk/problem/2407

---

題目大意

$n$個(gè)點(diǎn)的一張無(wú)向圖（但是正反權(quán)值不同），求一個(gè)從$1$出發(fā)回到$1$且不經(jīng)過(guò)重復(fù)邊的最短路徑。
$1\le n\le 10000,1\le m\le 2\times 10^5$

---

解題思路

考慮一個(gè)暴力的做法，枚舉一條出邊枚舉一條入邊，然后求出去的點(diǎn)到入點(diǎn)的最短路。

但是這樣如果點(diǎn)$1$度數(shù)很多就會(huì)$T$。

但是這種問(wèn)題配最短路是很經(jīng)典的套路，因?yàn)閮蓚€(gè)不同的數(shù)字至少有一個(gè)二進(jìn)制位不同，所以我們可以枚舉一個(gè)二進(jìn)制位，然后這個(gè)位為$1$的當(dāng)出邊，為$0$的當(dāng)入邊就好了。

時(shí)間復(fù)雜度$O((n+m){\log }^{2}m)$

---

code

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define mp(x,y) make_pair(x,y) using namespace std; const int N=11000; struct node{int to,next,w,id,ban; }a[N*40]; int n,m,tot,ans,ls[N],f[N];bool v[N]; priority_queue<pair<int,int> > q; inline char Getchar() {static char buf[100000],*p1=buf+100000,*pend=buf+100000;if(p1==pend){p1=buf; pend=buf+fread(buf,1,100000,stdin);if (pend==p1) return -1;}return *p1++; } inline int read() {char c;int d=1;int f=0;while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f; } void addl(int x,int y,int w,int id){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].id=id;return; } void dij(){memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));q.push(mp(0,1));f[1]=0;while(!q.empty()){int x=q.top().second;q.pop();if(v[x])continue;v[x]=1;for(int i=ls[x];i;i=a[i].next){if(a[i].ban)continue;int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;q.push(mp(-f[y],y));}}}return; } int main() {tot=1;n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read(),v=read();addl(x,y,w,i);addl(y,x,v,i);}ans=2147483647;for(int p=0;p<18;p++){for(int i=2;i<=tot;i++)if((a[i].id>>p)&1)a[i].ban=(a[i].to==1);else a[i].ban=(a[i^1].to==1);dij();for(int i=2;i<=tot;i++)if(!a[i].ban&&a[i].to==1)ans=min(ans,f[a[i^1].to]+a[i].w);}printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的bzoj#2407-探险【最短路,二进制分组】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。