這道題不難，但是map裡的一個操作也卡了我MLE
我之前用map去查詢的時候這麼寫t1=mp[tem];這樣不好的是如果tem不存在，會自動插入map一組值，導致內存消耗巨大。。。。改成傳統查詢方法就可以了。
言歸正傳，說說這道題，首先n^2的建圖是必然T的，然後就不會了，後來隊友提醒，連邊的條件給的很強，只能有一個位置不同或者有兩個位置不同但交換後便相同，這樣一個點的可能連邊數是10*9+10*9/2=135，復雜度馬上就下來了，诶，自己以後做題還是要多想想，善於挖掘條件！
[cpp]
#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;
}
#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;
}
