[PA2012]Tax

Description

给定一个图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。求 (1) 到 (n) 的最短路。

Solution

如果直接在这个图上跑的话，需要记录一下是从哪条边转移过来的，不太行。换一种思路，因为都是在和边打交道，不妨将边抽成点，建一个新图。点权就是原边权，边就是原图的点，边权就是新图两个点的较大值。但是这样的建图是 (m^2) 的。考虑到取 (max) 这个操作具有单调性。将原图一个点所连的边按边权排序后，一种权值对应的其实是一个前缀，所以考虑前缀优化。这样就可以直接跑了。注意建超级源汇点，以及拆边要拆成两条有向边。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef long long ll;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

const int N=1e5+7;
const int M=4e5+7;

int s,t,n,m;

struct E_{
    int id; ll w;
    E_(int id_=0,ll w_=0):id(id_),w(w_){}
    bool operator <(const E_ &X)const{return w>X.w;}
};

int head[M],cnt=1;
struct E{int next,to,w;}e[M<<5];

inline void add(int id,int to,int w){
    e[++cnt]=(E){head[id],to,w};
    head[id]=cnt;
//    printf("Link %d %d %d
",id,to,w);
}

ll dis[M];
priority_queue<E_> Q;
bool vis[M];
vector<E_> g[N];

int main(){
    n=read(),m=read();
    for(int i=1,u,v,w;i<=m;i++){
        u=read(),v=read(),w=read();
        g[u].push_back(E_(++cnt,w));
        g[v].push_back(E_(++cnt,w));
    }
    s=1,t=cnt+1; cnt=0;
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
        E_ lt; bool tag=0;
        for(E_ x:g[i]){
            if(tag){
                add(lt.id,x.id,0);
                add(x.id,lt.id,lt.w-x.w);
            }
            add(x.id,x.id^1,x.w);
            tag=1,lt=x;
        }
    }
    for(E_ x:g[1]) add(s,x.id,x.w);
    for(E_ x:g[n]) add(x.id^1,t,x.w);
    for(int i=s;i<=t;i++) dis[i]=1ll<<50;
    dis[s]=0,Q.push(E_(s,0));
    while(!Q.empty()){
        E_ t=Q.top(); Q.pop(); int u=t.id;
        if(vis[u]) continue; vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) Q.push((E_){v,dis[v]});
            }
        }
    }
    printf("%lld",dis[t]);
}