2015-02-28 13:54:35
思路:这题... O(n^2)建图显然是会T的。
所以我们应该更深入地考虑,如果枚举一个数字改变哪位改成什么,再枚举交换哪两位,那么每个数要枚举100+45次。50000 × 145还是可以接受的。
然后需要一个map,如果把数字看成字符串,用string作索引,还是会T,应该用long long来作索引...
之后就是根据最长公共前缀长度来建图,建完后跑Dij / Spfa即可。
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <queue>
10 #include <string>
11 #include <iostream>
12 #include <algorithm>
13 using namespace std;
14
15 #define MEM(a,b) memset(a,b,sizeof(a))
16 #define REP(i,n) for(int i=1;i<=(n);++i)
17 #define REV(i,n) for(int i=(n);i>=1;--i)
18 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19 #define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
21 #define MP(a,b) make_pair(a,b)
22
23 typedef long long ll;
24 typedef pair<int,int> pii;
25 const int INF = (1 << 30) - 1;
26 const int MAXN = 50005;
27
28 int n,cost[15];
29 ll s[MAXN];
30 int first[MAXN],ecnt;
31 int inq[MAXN],dis[MAXN];
32 int pre[MAXN];
33 ll fac[15];
34 map<ll,int> mp;
35
36 struct edge{
37 int v,next,c;
38 }e[MAXN * 200];
39
40 void Init(){
41 MEM(first,-1);
42 ecnt = 0;
43 fac[0] = 1;
44 REP(i,10) fac[i] = fac[i - 1] * 10LL;
45 }
46
47 void Add_edge(int u,int v,int c){
48 e[++ecnt].next = first[u];
49 e[ecnt].v = v;
50 e[ecnt].c = c;
51 first[u] = ecnt;
52 }
53
54 bool Spfa(){
55 queue<int> Q;
56 fill(dis + 1,dis + n + 1,INF);
57 dis[1] = 0;
58 MEM(inq,0);
59 MEM(pre,-1);
60 Q.push(1);
61 while(!Q.empty()){
62 int x = Q.front();
63 Q.pop();
64 inq[x] = 0;
65 for(int i = first[x]; ~i; i = e[i].next){
66 int v = e[i].v;
67 if(dis[v] == INF || dis[v] > dis[x] + e[i].c){
68 dis[v] = dis[x] + e[i].c;
69 pre[v] = x;
70 if(inq[v] == 0){
71 inq[v] = 1;
72 Q.push(v);
73 }
74 }
75 }
76 }
77 return dis[n] != INF;
78 }
79
80 void Print(){
81 int ans[MAXN],tot = 0;
82 for(int i = n; i != -1; i = pre[i])
83 ans[++tot] = i;
84 printf("%d\n",tot);
85 for(int i = tot; i > 1; --i)
86 printf("%d ",ans[i]);
87 printf("%d\n",ans[1]);
88 }
89
90 void Match(int a){
91 REP(i,10){
92 ll tem,tmp = s[a] - (s[a] % fac[i] / fac[i - 1]) * fac[i - 1];
93 for(int j = 0; j < 10; ++j){
94 tem = tmp + j * fac[i - 1];
95 if(tem != s[a] && mp.find(tem) != mp.end())
96 Add_edge(a,mp[tem],cost[11 - i]);
97 }
98 }
99 REP(i,10){
100 ll tem,v1 = s[a] % fac[i] / fac[i - 1],v2;
101 FOR(j,1,i - 1){
102 v2 = s[a] % fac[j] / fac[j - 1];
103 if(v1 == v2) continue;
104 tem = s[a] + (v2 - v1) * fac[i - 1] + (v1 - v2) * fac[j - 1];
105 if(mp.find(tem) != mp.end())
106 Add_edge(a,mp[tem],cost[11 - i]);
107 }
108 }
109 }
110
111 int main(){
112 Init();
113 scanf("%d",&n);
114 REP(i,10) scanf("%d",cost + i);
115 REP(i,n) scanf("%lld",&s[i]),mp[s[i]] = i;
116 REP(i,n) Match(i);
117 if(Spfa()){
118 printf("%d\n",dis[n]);
119 Print();
120 }
121 else printf("-1\n");
122 return 0;
123 }
转载于:https://www.cnblogs.com/naturepengchen/articles/4305304.html