P2446 [SDOI2010] 大陆争霸

2018-05-14 19:25:55


第一道迪杰斯特拉的题。。

还是参考了题解和@beretty 夫哥的板子

对于这道题来说。。

用d1,d2表示每一个城市的最早到达时间和最早进入时间

(毕竟不把它的小弟打掉也进不去)

然后优先队列里存的就是max(d1,d2)

用这个点的数去更新与它相连的点的d1

以及它控制的节点的d2

最后输出max(d1[n],d2[n])

堆优化是个好东西

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=3005;
struct edge
{
    int to,nxt,dis;
}edge[70005];
struct node
{
    int id,d;
    inline friend bool operator < (node a,node b)
    {
        return a.d>b.d;
    }
};
priority_queue<node>q;
int n,m,num,head[N],s[N][N],l[N],d1[N],d2[N];
bool vis[N];
//d1:最早能到达的时间
//d2:最早能进入的时间 
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    edge[num].dis=dis;
    head[from]=num;
}
inline int dijstra()
{
    memset(d1,127/3,sizeof(d1));
    d1[1]=0; q.push((node){1,0});
    while (!q.empty())
    {
        node now=q.top(); q.pop();
        int u=now.id,d=now.d;
        if (vis[u]) continue; vis[u]=1;
        for (reg int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if (d1[v]>d+edge[i].dis)
            {
                d1[v]=d+edge[i].dis;
                if (!l[v]) q.push((node){v,max(d1[v],d2[v])});
            }
        }
        for (reg int i=1;i<=s[u][0];i++)
        {
            int v=s[u][i];
            if (!--l[v])
            {
                d2[v]=d;
                q.push((node){v,max(d1[v],d2[v])});
            }
        }
    }
    return max(d1[n],d2[n]);
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add_edge(x,y,z);
    }
    for (reg int i=1;i<=n;i++)
    {
        l[i]=read();
        for (reg int j=1;j<=l[i];j++)
        {
            int now=read();
            s[now][++s[now][0]]=i;
        }
    }
    printf("%d\n",dijstra());
    return 0;
}