Luogu p6822 [pa2012]tax (shortest circuit + edge change point)

Luogu P6822 [PA2012]Tax（ shortest path + Edge change point ）

The question ：

Give a n A little bit m Undirected graph of strip and edge , The cost of passing through a point is the larger value of the edge weight of the two sides entering and leaving the point , Seek the starting point 1 point-to-point n The minimum cost of . The cost of starting point is the edge weight of the edge leaving the starting point , The cost of the destination is the edge weight of the edge entering the destination .

Ideas ：

Violence works wonders , Think of all the edges as points , if a->b,b>c, This connects the two sides as points , Finally, create a super source S, With 1 Connected points are connected , A weight of 0, Set up a super junction T, With n Connected points are connected . common m^2 side .

Consider optimizing ：

1. For a point , We sort the edges from small to large

2. Enumerate every edge , If this side is connected 1 perhaps N, So we're from S To or from this side T, The weight is the weight of the edge

3. Connect an edge from the corresponding incoming edge to the edge , Edge weights are their weights

4. Enumerate each outgoing edge , From the side with the smaller weight to the side with the larger weight to the side with the difference between the two sides , The connecting weight from the one with larger weight to the one with smaller weight is 0 The edge of

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
const int INF=0x3f3f3f;
typedef pair<ll,int>pii;
int n,m,k=1,k1=1,nex[maxn*2],head[maxn],to[maxn*2],ne[maxn*2];
int h[maxn],t[maxn*2],vis[maxn],p[maxn];
ll w[maxn*2],ww[maxn*2],dis[maxn];
void add(int x,int y,int z){
    
	nex[++k]=head[x];
	to[k]=y;
	head[x]=k;
	w[k]=z;
}
void pdd(int x,int y,int z){
    
	ne[++k1]=h[x];
	t[k1]=y;
	h[x]=k1;
	ww[k1]=z;
}
ll dij(){
    
	priority_queue<pii,vector<pii>,greater<pii>>q;
	for(int i=1;i<=maxn;i++)dis[i]=1e18;
	dis[0]=0;
	q.push({
    0,0});
	while(!q.empty()){
    
		int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=h[x];i;i=ne[i]){
    
			int y=t[i];
			if(dis[y]>dis[x]+ww[i]){
    
				dis[y]=dis[x]+ww[i];
				q.push({
    dis[y],y});
			}
		}
	}
	return dis[1];
}
bool cmp(int x,int y){
    
	return w[x]<w[y];
}
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++){
    
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
		pdd(k,k^1,z),pdd(k^1,k,z);
	}
	for(int i=1;i<=n;i++){
    
		int d=0;
		for(int j=head[i];j;j=nex[j])p[++d]=j;
		sort(p+1,p+d+1,cmp);
		for(int j=1;j<=d;j++){
    
			if(j!=1){
    
				pdd(p[j-1],p[j],w[p[j]]-w[p[j-1]]);
			    pdd(p[j],p[j-1],0);
			}
			if(i==1)pdd(0,p[j],w[p[j]]);
     		else if(i==n)pdd(p[j]^1,1,w[p[j]]);
		}
	}
	printf("%lld\n",dij());
}