BZOJ3045 电话线路

2014.12.11 08:18 Thu| 1 visits oi_2015| 2015_刷题日常| Text

Solution

一眼看去就是建边跑SPFA,但是建边的过程不清楚。其实可以开始的时候将每一个号码和它所对应的编号放入map中,之后对于每一个号码暴力找出它所能通话的所有号码,在set中查询是否存在这一号码,若存在,则可求出LCP,然后相应地连边,最终一次SPFA即可出解。每一个号码联通的串数不超过100+45=145个,因此此方法可行。在这一过程中手写hash表可以优化加速。

求出LCP的过程可以结合后缀数组,但是还是直接暴力更加实在~

这次正经是犯了和NOIP一模一样的错误,把std改的真的和我的程序一模一样了才发现。。。真的是该杀了……

Code

蒟蒻的沙茶代码

#include <bits/stdc++.h>
using namespace std;
#define ged(x,y) (x/p[y]%10)
#define N 50005
#define M 5000005
#define inf 0x3f3f3f3f

int n,a[N],d[N];
long long b[N],p[15];
int head[N],to[M],next[M],val[M],cnt;
priority_queue<pair<int,int> > q;
map<long long ,int> m;
map<long long ,int> ::iterator it;

inline void add(int x,int y)
{
    if(x==y) return;
    to[++cnt]=y;
    next[cnt]=head[x]; head[x]=cnt;
    int c;
    for(c=10;ged(b[x],c)==ged(b[y],c)&&c;c--);
    val[cnt]=a[c];
}

void spfa(int s)
{
    memset(d,0x3f,sizeof d);
    q.push(make_pair(0,s));d[s]=0;
    while(!q.empty())
    {
        int x=q.top().second,y=-q.top().first; q.pop();
        if(y!=d[x]) continue;
        y=0;
        for(int i=head[x];i;i=next[i])
            if(d[y=to[i]]>d[x]+val[i])
                d[y]=d[x]+val[i],
                q.push(make_pair(-d[y],y));
    }
}

int main()
{
    cin>>n;
    for(int i=10;i>=1;i--) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i], m[b[i]]=i;
    p[1]=1;
    for(int i=2;i<=10;i++) p[i]=p[i-1]*10;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=10;j++)
            for(int k=1;k<=10;k++)
                if((it=m.find(b[i]+p[j]*(k-ged(b[i],j))))!=m.end())
                    add(i,it->second);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=10;j++)
            for(int k=1;k<=10;k++)
                if((it=m.find(b[i]+p[j]*(ged(b[i],k)-ged(b[i],j))+p[k]*(ged(b[i],j)-ged(b[i],k))))!=m.end()) add(i,it->second);
    spfa(1);
    cout<<(d[n]==inf?-1:d[n])<<endl;
}

LYD神犇的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int u=100010,w=5000010;
int ver[w],edge[w],Next[w],head[u],pos[u],go[u],h[u],c[10],a[10],f[u][10],d[u],v[u],pre[u];
long long num[u],b[u],p[10],temp;
int n,m,tot,i,j,k,l,x,y;
queue<int> q;

void insert(long long x,int y)
{
    int z=x%99991;
    num[++tot]=x,pos[tot]=y,go[tot]=h[z],h[z]=tot;
}

int ask(long long x)
{
    int z=x%99991,i;
    for(i=h[z];i;i=go[i])
        if(num[i]==x) return pos[i];
    return 0;
}

void add(int x,int y)
{
    if(x==y) return;
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
    for(;f[x][edge[tot]]==f[y][edge[tot]];edge[tot]++);
    edge[tot]=a[edge[tot]];
}

void spfa()
{
    memset(d,0x3f,sizeof(d));
    q.push(1),d[1]=0,v[1]=1;
    while(q.size())
    {
        x=q.front(); q.pop(); v[x]=0;
        for(i=head[x];i;i=Next[i])
            if(d[ver[i]]>d[x]+edge[i])
            {
                d[ver[i]]=d[x]+edge[i];
                pre[ver[i]]=x;
                if(!v[ver[i]]) q.push(ver[i]),v[ver[i]]=1;
            }
    }
}

void print(int x)
{
    m++;
    if(x==1) {printf("%d\n%d",m,x); return;}
    print(pre[x]);
    printf(" %d",x);
}

int main()
{
    cin>>n;
    for(i=0;i<10;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]);
        insert(b[i],i);
        memset(c,0,sizeof(c));
        for(temp=b[i],m=0;temp;temp/=10) c[m++]=temp%10;
        for(j=0;j<10;j++) f[i][j]=c[10-j-1];
    }
    tot=0;
    for(p[0]=i=1;i<=10;i++) p[i]=p[i-1]*10;
    for(i=1;i<=n;i++)
    {
        memset(c,0,sizeof(c));
        for(temp=b[i],m=0;temp;temp/=10) c[m++]=temp%10;
        for(j=0;j<10;j++)
            for(k=0;k<10;k++)
            {
                if((l=ask(b[i]-c[j]*p[j]-c[k]*p[k]+c[k]*p[j]+c[j]*p[k]))) add(i,l);
                if((l=ask(b[i]-c[j]*p[j]+k*p[j]))) add(i,l);
            }
    }
    spfa();
    if(d[n]==0x3f3f3f3f) {puts("-1"); return 0;}
    cout<<d[n]<<endl;
    return 0;
}