BZOJ4289【PA2012】Tax <最短路>

Problem

【PA2012】Tax

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

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

Output

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

Sample Input

4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8

Sample Output

12

HINT

$N\le10^5$，$M\le2\times10^5$

标签：最短路

Solution

经典拆边建模。

将每条有向边作为一个点，若存在边$x:p\to q\;\lbrace c_1\rbrace$，$y:q\to r\;\lbrace c_2\rbrace$，则连边$x\to y\;\lbrace\max(c_1,c_2)\rbrace$。跑最短路即可。但这样图太稠密，会$\mathrm{TLE}$。

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

保险起见用$\mathrm{Dijkstra}$。

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;
}