[USACO07NOV]牛继电器Cow Relays (最短路,DP)

时间：2024-01-21 10:48:15

题目链接

Solution

  1. 非正解

    似乎比较蛇啊,先个一个部分分做法,最短路+\(DP\).

    在求最短路的堆或者队列中存储元素 \(dis_{i,j}\) 代表 \(i\) 这个节点,走了 \(j\) 条边的距离.

    然后跑堆优化 \(Dijkstra\) 或者 SPFA 即可.

    复杂度 \(O(N*nlog(n))\).

    其中 \(N\) 代表要走的边条数, \(n\) 代表节点数 . 但是这题 \(N\) 有 \(10^6\) ...

    洛谷上可以过掉 \(49\) 分.

    不过只要 \(N\) 小一点,这个算法明显更优啊...

  2. 正解

    虽然这题 \(N\) 很大,但是 \(n\) 超级小啊... 只有 \(10^2\) ...

    于是可以用 \(Floyd\) 跑最短路,然后呢??

    倍增。

    令 \(dis_{i,j,k}\) 代表从 \(i\) 到 \(j\) 走了 \(2^k\) 条边的最小距离.

    然后 \(Floyd\) 转移的时候利用和倍增跳 LCA 差不多的方式转移即可.

    (具体可以看代码)

    时间复杂度 \(O(n^3*log(N))\).

另外此题还需要一点离散化.

Code

49分:

#include<bits/stdc++.h>

using namespace std;

const int maxn=10008;

struct sj{int to,next,w;}a[maxn];

struct node{int u,k;};

int head[maxn],size,cnt;

int x[maxn],y[maxn],w[maxn];

int to[maxn],num,n,t,S,E;

map<int,int>dis[508],v[508];

map<int,int>js[508];

map<int,int>kkk;

int read()

{

    char ch=getchar(); int f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

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

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

    a[size].w=w;

}

void spfa()

{

    queue<node>q;

    q.push((node){S,0});

    dis[S][0]=0; v[S][0]=1;

    js[S][0]++;

    while(!q.empty())

    {

        node x=q.front();q.pop();

        int u=x.u,k=x.k;

        if(k==n)continue;

        for(int i=head[u];i;i=a[i].next)

        {

            int tt=a[i].to;

            if(!js[tt][k+1])dis[tt][k+1]=192608173,js[tt][k+1]++;

            if(dis[tt][k+1]>dis[u][k]+a[i].w)

            {

              dis[tt][k+1]=dis[u][k]+a[i].w;

              if(!v[tt][k+1])

              {

                q.push((node){tt,k+1});

                v[tt][k+1]=1;

              }

            }

        }

        v[u][k]=0;

    }

}

void pre()

{

    sort(to+1,to+num+1);

    int last=192608173;

    for(int i=1;i<=num;i++)

    {

        if(to[i]!=last)

        {

            kkk[to[i]]=++cnt;

            last=to[i];

        }

    }

    for(int i=1;i<=t;i++)

    {

        x[i]=kkk[x[i]],y[i]=kkk[y[i]];

        //cout<<x[i]<<' '<<y[i]<<endl;

        add(x[i],y[i],w[i]);

        add(y[i],x[i],w[i]);

    }

}

int main()

{

    n=read(); t=read(); S=read(); E=read();

    for(int i=1;i<=t;i++)

    {

        w[i]=read();

        x[i]=read(); y[i]=read();

        to[++num]=x[i]; to[++num]=y[i];

    }

    pre(); S=kkk[S],E=kkk[E];

    spfa();

    cout<<dis[E][n]<<endl;

}

100分:

#include<bits/stdc++.h>

using namespace std;

const int maxn=10008;

struct node{int u,k;};

int cnt;

int x[maxn],y[maxn],w[maxn];

int to[maxn],num,n,t,S,E;

int dis[508][508][22],ans[508][508];

map<int,int>kkk;

int read()

{

    char ch=getchar(); int f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

void floyd()

{

     for(int p=1;p<=20;p++)

     for(int k=1;k<=cnt;k++)

     for(int i=1;i<=cnt;i++)

     for(int j=1;j<=cnt;j++)

        dis[i][j][p]=min(dis[i][j][p],dis[i][k][p-1]+dis[k][j][p-1]);

}

void getans()

{

    memset(ans,127/2,sizeof(ans));

    int t=0,p=0;

    ans[0][S]=0;

    while(n)

    {

      if(n&1)

      {

          t=!t;

          for(int i=1;i<=cnt;i++)

          {

              ans[t][i]=2e9;

              for(int j=1;j<=cnt;j++)

              ans[t][i]=min(ans[t][i],ans[!t][j]+dis[i][j][p]);

          }

      }

      p++; n/=2;

    }

    cout<<ans[t][E];

}

#include<bits/stdc++.h>

using namespace std;

const int maxn=10008;

struct node{int u,k;};

int cnt;

int x[maxn],y[maxn],w[maxn];

int to[maxn],num,n,t,S,E;

int dis[508][508][22],ans[508][508];

map<int,int>kkk;

int read()

{

    char ch=getchar(); int f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

void floyd()

{

     for(int p=1;p<=20;p++)

     for(int k=1;k<=cnt;k++)

     for(int i=1;i<=cnt;i++)

     for(int j=1;j<=cnt;j++)

        dis[i][j][p]=min(dis[i][j][p],dis[i][k][p-1]+dis[k][j][p-1]);

}

void getans()

{

    memset(ans,127/2,sizeof(ans));

    int t=0,p=0;

    ans[0][S]=0;

    while(n)

    {

      if(n&1)

      {

          t=!t;

          for(int i=1;i<=cnt;i++)

          {

              ans[t][i]=2e9;

              for(int j=1;j<=cnt;j++)

              ans[t][i]=min(ans[t][i],ans[!t][j]+dis[i][j][p]);

          }

      }

      p++; n/=2;

    }

    cout<<ans[t][E];

}

void pre()

{

    sort(to+1,to+num+1);

    int last=192608173;

    for(int i=1;i<=num;i++)

    {

        if(to[i]!=last)

        {

            kkk[to[i]]=++cnt;

            last=to[i];

        }

    }

    for(int i=1;i<=t;i++)

    {

        x[i]=kkk[x[i]],y[i]=kkk[y[i]];

        dis[x[i]][y[i]][0]=dis[y[i]][x[i]][0]=w[i];

    }

}

int main()

{

    n=read(); t=read(); S=read(); E=read();

    memset(dis,127/3,sizeof(dis));

    for(int i=1;i<=t;i++)

    {

        w[i]=read();

        x[i]=read(); y[i]=read();

        to[++num]=x[i]; to[++num]=y[i];

    }

    pre(); S=kkk[S],E=kkk[E];

    floyd();

    getans();

}

void pre()

{

    sort(to+1,to+num+1);

    int last=192608173;

    for(int i=1;i<=num;i++)

    {

        if(to[i]!=last)

        {

            kkk[to[i]]=++cnt;

            last=to[i];

        }

    }

    for(int i=1;i<=t;i++)

    {

        x[i]=kkk[x[i]],y[i]=kkk[y[i]];

        dis[x[i]][y[i]][0]=dis[y[i]][x[i]][0]=w[i];

    }

}

int main()

{

    n=read(); t=read(); S=read(); E=read();

    memset(dis,127/3,sizeof(dis));

    for(int i=1;i<=t;i++)

    {

        w[i]=read();

        x[i]=read(); y[i]=read();

        to[++num]=x[i]; to[++num]=y[i];

    }

    pre(); S=kkk[S],E=kkk[E];

    floyd();

    getans();

}

相关文章