Description

給出一個(gè)N個(gè)點(diǎn)M條邊的無(wú)向圖，經(jīng)過(guò)一個(gè)點(diǎn)的代價(jià)是進(jìn)入和離開(kāi)這個(gè)點(diǎn)的兩條邊的邊權(quán)的較大值，求從起點(diǎn)1到點(diǎn)N的最小代價(jià)。起點(diǎn)的代價(jià)是離開(kāi)起點(diǎn)的邊的邊權(quán)，終點(diǎn)的代價(jià)是進(jìn)入終點(diǎn)的邊的邊權(quán)

N<=100000

M<=200000

Solution

這題關(guān)鍵在于化邊為點(diǎn)，把無(wú)向邊拆成2條有向邊

考慮最直白的一種建圖方法，對(duì)于每一個(gè)點(diǎn)u，它的每一條入邊向所有出邊連邊

但這樣邊數(shù)太多了，最壞是\(M^2\)條邊，不可行

考慮用差值來(lái)建圖，每條出邊向第一條比它大的出邊連一條權(quán)值為權(quán)差值的邊，并且反向連一條權(quán)值為0的邊

然后每條入邊向?qū)?yīng)的出邊連一條為自身權(quán)值的邊

設(shè)一個(gè)超級(jí)源點(diǎn)S和匯點(diǎn)T，S向1的所以出邊連邊，n的所以出邊向T連邊

這樣邊數(shù)是m級(jí)別的，然后跑最短路即可，

這題邊數(shù)較多，我用spfa過(guò)不了，用Dijkstra堆優(yōu)化可以過(guò)

Code

#include <cstdio> #include <algorithm> #include <queue> #include <cstring> #define ll long long #define Pa pair<ll,int> using namespace std;struct info{int to,nex,w;}e[400010],ne[2000010]; int n,m,tot=1,head[400010],nhead[400010],S,T; ll dis[400010]; priority_queue<Pa,vector<Pa>,greater<Pa> > q;inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; }inline void Link(int u,int v,int w){e[++tot].to=v;e[tot].w=w;e[tot].nex=head[u];head[u]=tot; }inline void nLink(int u,int v,int w){ne[++tot].to=v;ne[tot].w=w;ne[tot].nex=nhead[u];nhead[u]=tot; }bool cmp(int a,int b){return e[a].w<e[b].w;} int tmp[400010],tp; void Build(){tot=1;S=1,T=m*2+2;for(int i=1;i<=n;++i){tp=0;for(int j=head[i];j;j=e[j].nex) tmp[++tp]=j;sort(tmp+1,tmp+tp+1,cmp);for(int j=1;j<=tp;++j){int u=tmp[j],nex=tmp[j+1];if(e[u].to==n) nLink(u,T,e[u].w);if(i==1) nLink(S,u,e[u].w);nLink(u^1,u,e[u].w);if(j<tp) nLink(u,nex,e[nex].w-e[u].w),nLink(nex,u,0);}} }void Dijkstra(){for(int i=S;i<=T;++i)dis[i]=1ll<<60;q.push(make_pair(0,S));dis[S]=0;while(!q.empty()){int u=q.top().second;ll Dis=q.top().first; q.pop();if(Dis>dis[u]) continue;for(int i=nhead[u];i;i=ne[i].nex){int v=ne[i].to;if(dis[v]>dis[u]+ne[i].w){dis[v]=dis[u]+ne[i].w;q.push(make_pair(dis[v],v));} } } }int main(){n=read(),m=read();for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();Link(u,v,w);Link(v,u,w);}Build();Dijkstra();printf("%lld\n",dis[T]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/void-f/p/8537897.html

總結(jié)

以上是生活随笔為你收集整理的[Bzoj4289]PA2012 Tax（Dijkstra+技巧建图）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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