URAL 1806 - c++编程基础

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

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

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

[cpp]
#include
#include
#include
#include
#include
#include
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 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));
queueq;
q.push(0);
for(i=0;i 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 :: iterator pos;
mapmp;
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 for(i=0;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 if(i==0)printf("%d",v[i]);
else printf(" %d",v[i]);
puts("");
}
return 0;
}

#include
#include
#include
#include
#include
#include
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 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));
queueq;
q.push(0);

URAL 1806 (一)