bzoj 4289 PA2012 Tax——构图

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4289

可以把一个点上的边按权值排序，然后边权小的向第一个比它大的连差值的边，边权大的向第一个比它小的连0边；这样能体现出“边权较大的边的边权”。

别忘了每条边还要自己跟自己连自己权值的边，表示不是差值的初始值。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#define ll long long

using namespace std;

const int N=1e5+,M=2e5+;

int n,m,hd[M<<],xnt,to[M<<],nxt[M<<],w[M<<];

ll dis[M<<],ans=0x3f3f3f3f3f3f3f3f;//M<<1!v

bool vis[M<<];

struct Node{

  int bh,w;Node(int a=,int b=):bh(a),w(b) {}

};

vector<Node>e[N];

priority_queue<pair<ll,int> > q;

bool cmp(Node u,Node v){return u.w<v.w;}

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;

}

void dj()

{

  while(q.size())

    {

      int k=q.top().second;q.pop();

      if(vis[k])continue; vis[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        q.push(make_pair(-dis[v],v));

      }

    }

}

int main()

{

  n=rdn(); m=rdn();

  for(int i=,u,v,z;i<=m;i++)

    {

      u=rdn(); v=rdn(); z=rdn(); add(i,i+m,z); add(i+m,i,z);

      e[u].push_back(Node(i,z)); e[v].push_back(Node(i+m,z));

    }

  for(int i=;i<=n;i++)

    {

      sort(e[i].begin(),e[i].end(),cmp);

      int d=e[i].size();

      for(int j=;j<d-;j++)

    {

      add(e[i][j].bh,e[i][j+].bh,e[i][j+].w-e[i][j].w);

      add(e[i][j+].bh,e[i][j].bh,);

    }

    }

  memset(dis,0x3f,sizeof dis);

  int d=e[].size();

  for(int i=;i<d;i++)

    {

      dis[e[][i].bh]=e[][i].w;

      q.push(make_pair(-e[][i].w,e[][i].bh));

    }

  dj();

  d=e[n].size();

  for(int i=;i<d;i++)ans=min(ans,dis[e[n][i].bh]);

  printf("%lld\n",ans);

  return ;

}