[PA2012] Tax

トランスポートゲート:>Here<
題意:N個の点M辺の無方向図を与え、一つの点を通過する代価はこの点に入ると離れる二つの辺の辺権の大きい値であり、起点1から点Nまでの最小代価を求める.始点の対価は始点を離れる辺の辺権であり、終点の対価は終点に入る辺の辺権N<=10000000 M<=20000000である.
問題を解く構想.
この問題のデータにツッコミを入れるのは避けられないが、長調一午後は無果と標程が撮影に何の間違いもないのに、なぜかWAが限界データが標程と撮影された以上、権利があるのだろうか.
でもいい問題だ
まず、この問題の暴力的なやり方を考えます.各辺を新しい図の点として、元の図の点を列挙して、この点の隣接するすべての辺を遍歴して、大きさによって新しい図の中で縁を結んでいますが、このような辺の数は$M^2$に達しています.
エッジの数を最適化し、差分に使う考えを考えることができます.その中の1つのエッジを基準に、上へ行くには加算し、下へ行くには加算しません.基準となるこの辺は現在の経路の入辺であり,出辺については差分の辺に沿って歩くだけでよい.そこで、各点に隣接するすべてのエッジをソートし、隣接する隣接するエッジ--大きい方から小さい方への重み値を0、小さい方から大きい方への重み値を差とします.また、各エッジについて、その逆エッジは、基準としてその重み値がそのものであるエッジに接続されるべきですか?
Code

/*By DennyQi 2018.8.11*/
#include 
#include 
#include 
#include 
#define  r  read()
#define  lr lread()
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)using namespace std;
typedef long long ll;
const int MAXN = 2000010;
const int MAXM = 2000010;
const int INF = 1e18;
inline int read(){
    int x = 0; int w = 1; register int c = getchar();
    while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w;
}
inline int lread(){
    ll x = 0; int w = 1; register int c = getchar();
    while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w;
}
struct Edge{
    ll len;
    int idx;
}e[MAXM];
struct Dij{
    ll w;
    int idx;
};
inline bool operator < (const Dij& a, const Dij& b){
    return a.w > b.w;
}
int N,M,x,y,S,T,v,top;
int pfirst[MAXM],pnxt[MAXM],pto[MAXM],pnum_edge=-1;
ll pcost[MAXM],cost[MAXM],z;
int first[MAXM],nxt[MAXM],to[MAXM],num_edge=-1;
ll d[MAXM];
bool vis[MAXM];
priority_queue  q;
inline bool comp(const Edge& a, const Edge& b){
    return a.len < b.len;
}
inline void add(int u, int v, int w){
//    printf("%lld->%lld(%lld)
",u,v,w);
    to[++num_edge] = v;
    cost[num_edge] = w;
    nxt[num_edge] = first[u];
    first[u] = num_edge;
}
inline void padd(int u, int v, int w){
    pto[++pnum_edge] = v;
//    printf("num(%lld): %lld->%lld(%lld)
",pnum_edge,u,v,w);
    pcost[pnum_edge] = w;
    pnxt[pnum_edge] = pfirst[u];
    pfirst[u] = pnum_edge;
    if(u == 1){
        add(S, pnum_edge, w);
    }
    if(v == N){
        add(pnum_edge, T, w);
    }
}
inline void Dijkstra(int s){
    for(int i = 0; i <= T; ++i) d[i] = INF;
    d[s] = 0;
    q.push((Dij){0,s});
    ll u,v;
    while(!q.empty()){
        u = q.top().idx; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = first[u]; i != -1; i = nxt[i]){
            v = to[i];
            if(d[u] + cost[i] < d[v]){
                d[v] = d[u] + cost[i];
                q.push((Dij){d[v],v});
            }
        }
    }
}
int main(){
//    freopen(".in","r",stdin);
//    freopen("qxz.out","w",stdout);
    N = r, M = r;
    memset(pfirst,-1,sizeof(pfirst));
    memset(first,-1,sizeof(first));
    S = M*2+1;
    T = M*2+2;
//    printf("S = %lld  T = %lld
",S,T);
    for(int i = 1; i <= M; ++i){
        x = r, y = r, z = lr;
        padd(x, y, z);
        padd(y, x, z);
    }
    int v;
    for(int x = 2; x < N; ++x){
        top = 0;
        for(int i = pfirst[x]; i != -1; i = pnxt[i]){
            e[++top] = (Edge){pcost[i], i};
        }
        sort(e+1,e+top+1,comp);
        for(int i = 1; i <= top; ++i){
            if(i < top){
                add(e[i].idx, e[i+1].idx, e[i+1].len-e[i].len);
            }
            if(i > 1){
                add(e[i].idx, e[i-1].idx, 0);
            }
            add(e[i].idx^1, e[i].idx, e[i].len);
        }
    }
    Dijkstra(S);
    printf("%lld", d[T]);
    return 0;
}