BZOJ4289

BZOJ4289

Description

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

Input

第一行两个整数$N,M$表示共$N$个点$M$条边。
接下来的第$2$到$ M+1$行,一行三个整数$u,v,w$表示有一条从$u$到$v$边权为$w$的边。

Output

一行一个整数表示从$1$号点到$N$号点的最小代价

Sample Input

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

Sample Output

1
12

Solution

朴素的$M^2$级别的建图跑最短路肯定事跑不过这道题的,考虑优化边数,发现对于点$u$出发的一条边 $i$,它到所有点$u$出发的边的边权都是它自己的边权$w[i]$ ,而到所有$u$出发比它大的$j$的边权都是$w[j]=(w[j]-w[i])+w[i]$
所以可以利用类似网络流中的补流的方法,先把$u$出发的每个边按边权排序,每条边$E[j](E[j]是边的序号,下同)$和它对应的反向边E[j]^1连一条边权为它本身边权$w[E[j]]$的边,然后对于第$j$大的边$E[j]$只用向$E[j-1]$连边权为$0$的边,向$E[j+1]$连边权为$w[E[j+1]]-w[E[j]]$的边,而起点$1$出发的边和到达终点$N$的边也是分别连$S到E[j]$和$E[j]到T$就是了
图建完了就最短路随便瞎搞
注意本题要开$long\ long$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define FIO "4289"
#define INF 0x3f3f3f
#define xx first
#define yy second
#define pli pair<ll,int>
typedef long long ll;
const int MOD=1e9+7,MAXN=1e5+5,MAXM=2e5+5;
using namespace std;
char buf[1<<20]; int bufl,bufr;
#define getch ((bufl^bufr||(bufl=0,bufr=fread(buf,1,1<<20,stdin)))?buf[bufl++]:EOF)
template <class T>inline void read (T &x) {
T f=1;
x=0;
char ch=getchar();
for (; !isdigit (ch)&&ch!='-'; ch=getchar());
if (ch=='-')f=-1,ch=getchar();
for (; isdigit (ch); ch=getchar())x=x*10+ch-'0';
x*=f;
}
int n,m,u,v,w,S,T;
namespace graph {
int head[MAXM<<1],nxt[MAXM*6],to[MAXM*6],va[MAXM*6],ecnt;
ll dis[MAXM<<1];
inline void add (int u,int v,int w) {
nxt[++ecnt]=head[u];
head[u]=ecnt;
to[ecnt]=v;
va[ecnt]=w;
}
inline void dijkstra() {
memset (dis,INF,sizeof dis);
static priority_queue<pli,vector<pli>,greater<pli> > q;
q.push (pli (0ll,S));
while (!q.empty()) {
pli u=q.top(); q.pop();
if (dis[u.yy]<u.xx) continue;
for (int i=head[u.yy]; i; i=nxt[i]) if (u.xx+va[i]<dis[to[i]])
dis[to[i]]=u.xx+va[i],q.push (pli (dis[to[i]],to[i]));
}
printf ("%lld\n",dis[T]);
}
};
namespace ori {
int head[MAXN],to[MAXM<<1],nxt[MAXM<<1],va[MAXM<<1],ecnt=1;
inline bool cmp (const int &x,const int &y) {
return va[x]<va[y];
}
inline void add (int u,int v,int w) {
nxt[++ecnt]=head[u];
head[u]=ecnt;
to[ecnt]=v;
va[ecnt]=w;
}
inline void build() {
S=1; T=ecnt+1;
static int a[MAXM],t=0;
for (int i=1; i<=n; i++) {
t=0;
for (int j=head[i]; j; j=nxt[j]) a[++t]=j;
sort (a+1,a+t+1,cmp);
for (int j=1; j<=t; j++) {
if (i==1) graph::add (S,a[j],va[a[j]]);
if (to[a[j]]==n) graph::add (a[j],T,va[a[j]]);
if (j^1) graph::add (a[j],a[j-1],0);
if (j^t) graph::add (a[j],a[j+1],va[a[j+1]]-va[a[j]]);
graph::add (a[j]^1,a[j],va[a[j]]);
}
}
}
};
int main() {
freopen (FIO".in","r",stdin);
freopen(FIO".out","w",stdout);
read (n); read (m);
for (int i=1; i<=m; i++)
read (u),read (v),read (w),ori::add (u,v,w),ori::add (v,u,w);
ori::build();
graph::dijkstra();
return 0;
}