codeforces(D. Navigation System)堆优化dijsktra算法

前天晚上的div2的一道题

原题链接:https://codeforces.com/contest/1321/problem/D

大体意思是给你一个有向图,并给你一个导航,每次导航都会给你计算出最短路,但又给了你一个路径,必须按照给的这个路径走,每走到一个点,导航有可能都会重新计算从这个点到终点的最短路径,问导航计算的最少次数和最大次数是多少。

经大佬点播了一下,要反向建图,然后dijsktra求最后一个点到所有点的最短路,再正着走一遍即可

但敲完之后交上去超时了?

唉....真是孤陋寡闻.....1e5个点用我之前的朴素dijsktra轻轻松松超时

才知道,dijsktra有堆优化......

这里堆优化就是用一个优先队列存储一个点到下一个点的最短距离,用的时候直接O(1)出队即可

 

原题代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct qq
{
    int to;
    int w;
    int next;
}q[200010];
struct qqq
{
    int to;
    int w;
    int next;
}e[200010];
struct node
{
    int val;
    int num;
    bool operator <(const node &a)const{
        return a.val<val;
    }
};
priority_queue<node>que;
int head[200010],head2[200010],a[200010],dis[200010],book[200010],inf=99999999,n,m;
void dijsktra(int s)
{
    for(int i=1;i<=n;i++)
    {dis[i]=inf;}
    dis[s]=0;
    node e;
    e.val=dis[s];e.num=s;
    que.push(e);
    while(!que.empty())
    {
        node u=que.top();
        que.pop();
        if(book[u.num]!=0)
        {continue;}
        book[u.num]=1;
        for(int j=head[u.num];j!=-1;j=q[j].next)
        {
            if(dis[q[j].to]>dis[u.num]+q[j].w)
            {
                dis[q[j].to]=dis[u.num]+q[j].w;
                if(book[q[j].to]==0)
                {
                    node tmp;
                    tmp.num=q[j].to;
                    tmp.val=dis[q[j].to];
                    que.push(tmp);
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n+1;i++)
    {head[i]=-1;head2[i]=-1;}
    int t1,t2;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&t2,&t1);
        //反向建图
        q[i].to=t2;
        q[i].w=1;
        q[i].next=head[t1];
        head[t1]=i;
        //正向建图
        e[i].to=t1;
        e[i].w=1;
        e[i].next=head2[t2];
        head2[t2]=i;
    }
    int p;
    scanf("%d",&p);
    for(int i=0;i<p;i++)
    {scanf("%d",&a[i]);}
    int s=a[p-1];
    dijsktra(s);
    int l=0,r=0;
    for(int i=1;i<p;i++)
    {
        if(dis[a[i]]>=dis[a[i-1]])
        {l++;r++;}
        else
        {
            int d=a[i-1];
            for(int j=head2[d];j!=-1;j=e[j].next)
            {
                if(dis[e[j].to]<=dis[a[i]]&&e[j].to!=a[i])
                {r++;break;}
            }
        }
    }
    cout<<l<<" "<<r<<endl;
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注