学步园

这道题不难，但是map里的一个操作也卡了我MLE

我之前用map去查询的时候这么写t1=mp[tem];这样不好的是如果tem不存在，会自动插入map一组值，导致内存消耗巨大。。。。改成传统查询方法就可以了。

言归正传，说说这道题，首先n^2的建图是必然T的，然后就不会了，后来队友提醒，连边的条件給的很强，只能有一个位置不同或者有两个位置不同但交换后便相同，这样一个点的可能连边数是10*9+10*9/2=135，复杂度马上就下来了，诶，自己以后做题还是要多想想，善于挖掘条件！

#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
typedef long long ll;
using namespace std;
const int inf=((~(0U))>>1);
int head[50010],cnt;
struct Edge{
    int v,w,next;
}edge[20001000];

int val[20],n;
ll s[50010],tem,t1,t2;
ll p[20];
bool vis[50010];
int pre[50010],dp[50010];
vector <int>v;
void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}

void addedge(int u,int v,int w){
    int i;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

bool spfa(){
    int i,u,v;
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(0);
    for(i=0;i<n;i++) dp[i]=inf;
    dp[0]=0;vis[0]=1;
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next){
            v=edge[i].v;
            if(dp[v]==inf || dp[v]>dp[u]+edge[i].w){
                dp[v]=dp[u]+edge[i].w;
                pre[v]=u;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dp[n-1]==inf)return 0;
    return 1;
}

void print(int now){
    if(now==0) return ;
    print(pre[now]);
    //printf("%d ",pre[now]+1);
    v.push_back(pre[now]+1);
}

int main(){
    map<ll,int> :: iterator pos;
    map<ll,int>mp;
    int i,j,k;
    p[0]=1;
    for(i=1;i<=10;i++) p[i]=p[i-1]*10;
    scanf("%d",&n);
    init();
    for(i=0;i<10;i++) scanf("%d",&val[i]);
    for(i=0;i<n;i++) scanf("%I64d",&s[i]),mp[s[i]]=i;
    for(i=0;i<n;i++){
        for(j=0;j<10;j++){
            for(k=0;k<10;k++){
                tem=s[i];
                t1=(s[i]%p[10-j])/p[9-j];
                if(k==t1) continue;
                tem=tem-t1*p[9-j]+p[9-j]*k;
                pos=mp.find(tem);
                if(pos!=mp.end()) addedge(i,pos->second,val[j]);
            }
        }
        for(j=0;j<10;j++)
            for(k=j+1;k<10;k++){
                tem=s[i];
                t1=(s[i]%p[10-j])/p[9-j];
                t2=(s[i]%p[10-k])/p[9-k];
                if(t1==t2)continue;
                tem=tem-t1*p[9-j]-t2*p[9-k]+t2*p[9-j]+t1*p[9-k];
                pos=mp.find(tem);
                if(pos!=mp.end()) addedge(i,pos->second,val[j]);
            }
    }
    bool t3=spfa();
    if(t3==0){
        printf("-1\n");
        return 0;
    }
    else{
        printf("%d\n",dp[n-1]);
        print(n-1);
        v.push_back(n);
        printf("%d\n",v.size());
        for(i=0;i<v.size();i++)
            if(i==0)printf("%d",v[i]);
            else printf(" %d",v[i]);
        puts("");
    }
    return 0;
}