[Bzoj4289]PA2012 Tax（Dijkstra+技巧建图）

Description

给出一个N个点M条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点1到点N的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权

N<=100000

M<=200000

Solution

这题关键在于化边为点，把无向边拆成2条有向边

考虑最直白的一种建图方法，对于每一个点u，它的每一条入边向所有出边连边

但这样边数太多了，最坏是\(M^2\)条边，不可行

考虑用差值来建图，每条出边向第一条比它大的出边连一条权值为权差值的边，并且反向连一条权值为0的边

然后每条入边向对应的出边连一条为自身权值的边

设一个超级源点S和汇点T，S向1的所以出边连边，n的所以出边向T连边

这样边数是m级别的，然后跑最短路即可，

这题边数较多，我用spfa过不了，用Dijkstra堆优化可以过

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;

}