专栏首页数据结构与算法BZOJ 4289: PA2012 Tax(最短路)

BZOJ 4289: PA2012 Tax(最短路)

Description

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

N<=100000

M<=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 second
const 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HUST 1017 - Exact cover

    Time Limit: 15s Memory Limit: 128MB Special Judge Submissions: 7636 Solved: 38...

    attack
  • P1629 邮递员送信

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • HUST 1017 - Exact cover

    Time Limit: 15s Memory Limit: 128MB Special Judge Submissions: 7636 Solved: 38...

    attack
  • P1629 邮递员送信

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • HDU 1863 畅通工程

    一道很朴素的最小生成树,不过通过此题知道了,当n已经决定的情况下,若n个点无法构成最小生成树的话,最终得到ans无法得到精确的值,他会将无穷大的路径加入。 #i...

    用户1624346
  • P1983 车站分级

    题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

    attack
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券