BZOJ 4289: PA2012 Tax(最短路)

2018-02-27 08:59:42来源:cnblogs.com作者:自为风月马前卒人点击

分享
Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 755  Solved: 240
[Submit][Status][Discuss]

Description

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

Input

 

Output

 

Sample Input

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

Sample Output

12

HINT


Source

这题居然卡long long,也是没谁了

首先一个很显然的思路是暴力拆边

即把每个点每一条入边和每一条出边的两两看做一个点,权值为两边的较大值

但是这样很显然是$O(m^2)$,肯定会GG

所以我们考虑一种神仙操作。

对于一条无向边,我们把它看成两条有向边

然后我们这样构图

1.对于一个点,我们把它的出边从小到大排序

2.枚举每一条边,如果这条边连接着1或者N,那么我们从S连向这条边或者从这条边连向T,权值为该边的权值

3.从改边所对应的入边向该边连一条边,边权为它们的权值

4.枚举每一条出边,从权值较小的向权值较大的连权值为两边差值的边,从权值较大的向权值较小的连权值为0的边

可能这样说不是很清楚,借鉴一下这位大佬的图

#include<cstdio>#include<algorithm>#include<queue>#include<cstring>#define Pair pair<long long,int>#define F first#define S secondconst int MAXN=2*1e6+10;using namespace std;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct Edge{    int u,v,w,nxt;}E[MAXN];int headE[MAXN],numE=2;inline void add_edge(int x,int y,int z){    E[numE].u=x;    E[numE].v=y;    E[numE].w=z;    E[numE].nxt=headE[x];    headE[x]=numE++;}struct node{    int u,v,w,nxt;}edge[MAXN];int head[MAXN],num=2;inline void AddEdge(int x,int y,int z){    edge[num].u=x;    edge[num].v=y;    edge[num].w=z;    edge[num].nxt=head[x];    head[x]=num++;}int N,M,S,T;int temp[MAXN];long long  dis[MAXN];bool vis[MAXN];void Dijstra(){    memset(dis,0xf,sizeof(dis));dis[S]=0;    priority_queue<Pair>q;    q.push(make_pair(0,S));    while(q.size()!=0)    {        while(vis[q.top().second]&&q.size()>0) q.pop();        long long  p=q.top().second;        vis[p]=1;        for(int i=head[p];i!=-1;i=edge[i].nxt)            if(dis[edge[i].v]>dis[p]+edge[i].w)                dis[edge[i].v]=dis[p]+edge[i].w,                q.push(make_pair(-dis[edge[i].v],edge[i].v));    }    printf("%lld/n",dis[T]);}int comp(const int &a,const int &b){    return E[a].w<E[b].w;}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    memset(headE,-1,sizeof(headE));    memset(head,-1,sizeof(head));    N=read();M=read();S=1,T=2*(M+1);    for(int i=1;i<=M;i++)    {        int x=read(),y=read(),z=read();        add_edge(x,y,z);        add_edge(y,x,z);    }    for(int i=1;i<=N;i++)    {        int tempnum=0;        for(int j=headE[i];j!=-1;j=E[j].nxt)            temp[++tempnum]=j;        sort(temp+1,temp+tempnum+1,comp);        for(int j=1;j<=tempnum;j++)        {            int x=temp[j],y=temp[j+1];            if(E[x].u==1)                 AddEdge(S,x,E[x].w);            if(E[x].v==N)                 AddEdge(x,T,E[x].w);            AddEdge(x^1,x,E[x].w);            if(j!=tempnum)                AddEdge(x,y,E[y].w-E[x].w),                AddEdge(y,x,0);        }    }    Dijstra();    return 0;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台