BZOJ4289

BZOJ , , 评论

BZOJ4289

Description

给出一个个点条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点到终点的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。 ### Input 第一行两个整数表示共个点条边。 接下来的第到$ M+1行，一行三个整数u,v,w表示有一条从u到v边权为w$的边。 ### Output 一行一个整数表示从号点到号点的最小代价

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

朴素的级别的建图跑最短路肯定事跑不过这道题的，考虑优化边数，发现对于点出发的一条边 ，它到所有点出发的边的边权都是它自己的边权 ,而到所有出发比它大的的边权都是 所以可以利用类似网络流中的补流的方法，先把出发的每个边按边权排序，每条边是边的序号，下同）和它对应的反向边E[j]^1连一条边权为它本身边权的边，然后对于第大的边只用向连边权为的边，向连边权为的边，而起点出发的边和到达终点的边也是分别连到和到就是了 图建完了就最短路随便瞎搞 注意本题要开 ### 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
82
#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;
}

不知不觉Acmer & Student

Never Settle