首页 > 代码库 > 「Poetize7」电话线路
「Poetize7」电话线路
描述
每台电话都有一个独一无二的号码，用一个十位的十进制数字串表示。电话a和b之间能直接通信，当且仅当“a与b之间仅有一个数字不同”，或者“交换a的某 两位上的数字后，a与b相同”。而a、b之间建立通信联系所需要的时间为cost[ lcp(a,b) ]，其中cost[]是一个常数数 组，lcp(a,b)表示a、b的最长公共前缀的长度，lcp(a,b)越大，通信时间越快。
另外，如果a、b能通信，b、c能通信，那么a、c也能借助b来通信。a、c借助b建立通信联系所用时间是cost[ lcp(a,b) ]+ cost[ lcp(b,c) ]。
现在Freda想给Rainbow打电话，请你告诉Freda，她最快需要多少时间才能与与Rainbow建立通信联系？
题解：
这题也比较裸。
直接枚举每个电话号码能与谁连边，然后构图spfa即可。
关键在于把时间复杂度降下来。
我写的map T了5个点。。。
后来好好想了想改成hash没用heap+dij 和 slf优化 ，朴素的spfa也过了。
代码：AC
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50000+10014 #define maxm 100000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 99999123 using namespace std;24 inline ll read()25 {26 ll x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 map<string,int>mp;32 struct edge{ll go;int next,w;}e[100*maxn],f[maxn];33 int n,m,tot,head[maxn],h[mod],v[maxn],q[maxn+1],d[maxn],cost[15];34 ll a[15],b[15];35 string s[maxn],ss;36 char st[maxn];37 inline void insert(int x,int y,int z)38 {39 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z;40 e[++tot].go=x;e[tot].next=head[y];head[y]=tot;e[tot].w=z;41 }42 inline int hash(ll x)43 {44 int y=x%mod;45 for(int i=h[y];i;i=f[i].next)46 if(f[i].go==x)return i;47 return 0;48 } 49 void spfa()50 {51 for1(i,n)d[i]=inf;52 int l=0,r=1;q[1]=1;d[1]=0;53 while(l!=r)54 {55 int x=q[++l];v[x]=0;if(l==maxn)l=0;56 for(int i=head[x],y;i;i=e[i].next)57 if(d[x]+e[i].w<d[y=e[i].go])58 {59 d[y]=d[x]+e[i].w;60 if(!v[y]){q[++r]=y;v[y]=1;if(r==maxn)r=0;}61 }62 }63 }64 int main()65 {66 freopen("input.txt","r",stdin);67 freopen("output.txt","w",stdout);68 n=read();69 for0(i,9)cost[i]=read();70 b[0]=1;for1(i,9)b[i]=b[i-1]*10;71 for1(i,n)72 {73 ll x=read(),y=x%mod,t=x;74 f[i].go=x;f[i].next=h[y];h[y]=i;75 for0(j,9)a[j]=t%10,t/=10;76 for0(j,9)77 for0(k,9)78 {79 if(j!=k&&a[j]!=a[k])80 {81 t=x-a[j]*b[j]-a[k]*b[k]+a[j]*b[k]+a[k]*b[j];82 y=hash(t);83 if(y)insert(i,y,cost[9-max(j,k)]);84 }85 if(a[j]!=k)86 {87 t=x-a[j]*b[j]+(ll)k*b[j];88 y=hash(t);89 if(y)insert(i,y,cost[9-j]);90 }91 }92 }93 spfa();94 printf("%d\n",d[n]==inf?-1:d[n]);95 return 0;96 }
代码：map
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 50000+100 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 map<string,int>mp; 61 struct edge{int go,next,w;}e[100*maxn]; 62 int n,m,tot,head[maxn],v[maxn],q[maxn+1],d[maxn],cost[15]; 63 string s[maxn],ss; 64 char st[maxn]; 65 inline void insert(int x,int y,int z) 66 { 67 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z; 68 } 69 void spfa() 70 { 71 for1(i,n)d[i]=inf; 72 int l=0,r=1;q[1]=1;d[1]=0; 73 while(l!=r) 74 { 75 int x=q[++l];v[x]=0;if(l==maxn)l=0; 76 for(int i=head[x],y;i;i=e[i].next) 77 if(d[x]+e[i].w<d[y=e[i].go]) 78 { 79 d[y]=d[x]+e[i].w; 80 if(!v[y]){q[++r]=y;v[y]=1;if(r==maxn)r=0;} 81 } 82 } 83 } 84 85 int main() 86 87 { 88 89 n=read(); 90 for0(i,9)cost[i]=read(); 91 for1(i,n){scanf("%s",st);s[i]=st;mp[s[i]]=i;} 92 for1(i,n) 93 { 94 ss=s[i]; 95 for0(j,9) 96 for0(k,9) 97 if(ss[j]-‘0‘!=k) 98 { 99 ss[j]=k+‘0‘;100 int x=mp[ss];101 if(x)insert(i,x,cost[j]);102 ss[j]=s[i][j];103 }104 for0(j,9)105 for0(k,9)106 if(j!=k&&ss[j]!=ss[k])107 {108 swap(ss[j],ss[k]);109 int x=mp[ss];110 if(x)insert(i,x,cost[min(j,k)]);111 swap(ss[j],ss[k]);112 }113 }114 spfa();115 printf("%d\n",d[n]==inf?-1:d[n]);116 117 return 0;118 119 }
「Poetize7」电话线路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。