BZOJ4289【PA2012】Tax <最短路>

Problem

【PA2012】Tax

Description

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

Input

第一行两个整数，表示图的点数和边数。
接下来行，每行三个整数，表示间存在一条边权为的无向边。

Output

输出一行一个整数，表示从到的最小代价。

Sample Input

Sample Output

HINT

，

标签：最短路

Solution

经典拆边建模。

将每条有向边作为一个点，若存在边，，则连边。跑最短路即可。但这样图太稠密，会。

考虑像网络流一样差分建图。对于点，记录其入边和出边，并将按边权排序。对于每对互为反向边的边，从入边向出边连边权为原边权的边。对于排好序的，按顺序从小到大，每条边向其下一条边连一条长为原边权差的点。这样相当于每个点的出边集连成了一条链，选择在链的哪个部分离开即可确定在原图上走哪条出边。

保险起见用。

Code

#include <bits/stdc++.h>
#define MAX_N 400000
#define mp make_pair
#define fir first
#define sec second
using namespace std;
typedef long long lnt;
typedef pair<lnt,int> pli;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, val[MAX_N+5];
vector <int> G[MAX_N+5], E[MAX_N+5];
vector <int> g[MAX_N+5], r[MAX_N+5];
struct node {int u, v, c;} a[MAX_N+5];
bool cmp (const node &p, const node &q) {return p.c < q.c;}
void insert(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void ins(int u, int v, int c) {g[u].push_back(v), r[u].push_back(c);}
lnt Dijkstra() {
    lnt dis[MAX_N+5]; memset(dis, 127, sizeof dis);
    priority_queue <pli> que; que.push(mp((dis[s] = 0), s));
    while (!que.empty()) {
        int u = que.top().sec; lnt d = que.top().fir;
        que.pop(); if (dis[u] != -d) continue;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i], c = E[u][i];
            if (dis[u]+c >= dis[v]) continue;
            dis[v] = dis[u]+c, que.push(mp(-dis[v], v));
        }
    }
    return dis[t];
}
int main() {
    read(n), read(m), s = 1, t = m*2+2;
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), 
        val[i*2] = val[i*2+1] = c, 
        ins(u, i*2, i*2+1), 
        ins(v, i*2+1, i*2);
    for (int i = 2, tot = 0; i < n; i++, tot = 0) {
        for (int j = 0; j < (int)g[i].size(); j++)
            a[++tot] = (node){r[i][j], g[i][j], val[g[i][j]]};
        sort(a+1, a+tot+1, cmp);
        for (int j = 1; j <= tot; j++) insert(a[j].u, a[j].v, a[j].c);
        for (int j = 1; j < tot; j++) insert(a[j].v, a[j+1].v, a[j+1].c-a[j].c);
        for (int j = 1; j < tot; j++) insert(a[j+1].v, a[j].v, 0);
    }
    for (int i = 0; i < (int)g[1].size(); i++) insert(s, g[1][i], val[g[1][i]]);
    for (int i = 0; i < (int)g[n].size(); i++) insert(r[n][i], t, val[g[n][i]]);
    return printf("%lld\n", Dijkstra()), 0;
}