磁力搜()是一个基于DHT协议的BT磁力搜索引擎，所有资源均来自DHT网络。磁力搜索服务器仅收录磁力链接信息，并不存储任何资源和种子文件。因此经由本站搜索所产生的任何结果皆不代表本站立场，本站不对其真实合法性以及版权负责，亦不承担任何法律责任。
磁力链接()是一种新型的分享形式，每个链接对应一个BT种子文件。您可以通过软件下载磁力链接指向的资源，例如迅雷、BitComet、QQ旋风，也可以使用云点播服务在线观看影视资源，例如迅雷云播、百度云盘等。
网站备案 : 蜀ICP备号-4Problem:1041
Solution_ID:23525& && && && &可以用宏定义解决此题
& && && && & & && &时间复杂度：Θ（O（1）) 空间复杂度：Θ（O（1）)
#include&cstdio&#include&iostream&#include&cmath&#include&cstring&#define dis(a,b) sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))#define One
int n,s,t,a,b,ti,x[405],y[405];#define day double w[405][405],ans[15];#define The void last_point(int i,int ti)#define Most {#define Handsome double temp=0;#define
Man int p=0;#define who w[i-1][i-2]=w[i-2][i-1]=dis(i-1,i-2);#define named
w[i-1][i-3]=w[i-3][i-1]=dis(i-1,i-3);#define xBegin
w[i-2][i-3]=w[i-3][i-2]=dis(i-2,i-3);#define Starx
if(w[i-1][i-2]&w[i-1][i-3]) {#define was
p=1;temp=w[i-1][i-2];}#define walking
else {p=2;temp=w[i-1][i-3];}#define on
if(w[i-2][i-3]&temp) p=3;#define road
switch(p){#define Suddenly
case 1:#define he
x[i]=x[i-1]+x[i-2]-x[i-3];#define saw
y[i]=y[i-1]+y[i-2]-y[i-3];#define a_#define young
case 2:#define people
x[i]=x[i-1]+x[i-3]-x[i-2];#define whose
y[i]=y[i-1]+y[i-3]-y[i-2];#define #define is
case 3:#define xx
x[i]=x[i-2]+x[i-3]-x[i-1];#define D
y[i]=y[i-2]+y[i-3]-y[i-1];#define R#define G
}#define xxx
for(int j=1;j&=3;j++)#define
w[i][i-j]=w[i-j][i]=ti*dis(i,i-j);#define begin
w[i-1][i-2]=w[i-2][i-1]*=#define star
w[i-1][i-3]=w[i-3][i-1]*=#define immediately
w[i-2][i-3]=w[i-3][i-2]*=ti##define in }#define order void line(int i,int t)#define to {#define see for(int k=0;k&=3;k++)#define and_
for(int j=1;j&=i-4;j++)#define record
w[i-k][j]=w[j][i-k]=t*dis(i-k,j);#define what }#define DRG int main(){#define would
cin&&n;#define
do_ memset(ans,0x7f,sizeof(ans));#define begin_star
for(int ii=1;ii&=n;ii++)#define found
memset(w,0x7f,sizeof(w));#define put
memset(x,0,sizeof(x));#define up
memset(y,0,sizeof(y));#define his
cin&&s&&t&&a&&b;#define right
s*=4,a*=4,b*=4;#define hand
for(int i=1;i&=s;i++)#define ran
{#define tohim
for(int j=1;j&=3;j++,i++)#define
cin&&x[i]&&y[i];#define xbegin
cin&&#define starx
last_point(i,ti);#define asked
line(i,t);#define Drg
}#define why
for(int k=1;k&=s;k++)#define done
for(int i=1;i&=s;i++)#define so
for(int j=i;j&=s;j++)#define the
w[i][j]=min(w[i][j],w[i][k]+w[k][j]);#define dRg
if(a==b) ans[ii]=0.0;#define said
else for(int i=0;i&=3;i++)#define you
for(int j=0;j&=3;j++)#define have
ans[ii]=min(ans[ii],w[a-i][b-j]);#define too
}#define much
for(int i=1;i&=n;i++)#define du
printf("%.1lf\n",ans[i]);#define THE
return 0;#define END }One day The Most Handsome Man who named xBegin Starx was walking on roadSuddenly he saw a_ young people whose name is xx D R G xxx then begin star immediately stoped in order to see and_ record what DRG would do_begin_star found drg put up his right hand ran tohim
when xbegin starx asked Drg why done so the dRg saidyou have too much duTHE END
by 47799 十一月 17,
Solution_ID:22842& && && && &巨水
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&#include&cstdio&#include&cmath&struct node{int x,y;}h[500];double minnn(double x,double y){return x&y?y:x;}double qjl(int x1,int y1,int x2,int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double qjll(node a1,node a2){return qjl(a1.x,a1.y,a2.x,a2.y);}double minnn4(double a,double b,double c,double d){return minnn(minnn(a,b),minnn(c,d));}int main(){scanf("%d",&o);for (int owo=1;owo&=o;owo++){int s,t,A,B,tt=0;scanf("%d%d%d%d", &s, &t, &A, &B);double dis[500][500];for(int i=0;i&4*s+1;i++)for(int j=0;j&4*s+1;j++)dis[i][j]=1e8;for(int i=0;i&=s-1;i++){int x1,y11,x2,y2,x3,y3,x4,y4,scanf("%d%d%d%d%d%d%d",&x1,&y11,&x2,&y2,&x3,&y3,&tt);double g1=qjl(x1,y11,x2,y2),g2=qjl(x1,y11,x3,y3),g3=qjl(x2,y2,x3,y3);if(g2&=g1&&g2&=g3){x4=x3+x1-x2;y4=y3+y11-y2;}if(g1&=g2&&g1&=g3){x4=x2+x1-x3;y4=y2+y11-y3;}if(g3&=g1&&g3&=g2){x4=x3+x2-x1;y4=y3+y2-y11;}h[4*i+1]=(node){x1,y11};h[4*i+2]=(node){x2,y2};h[4*i+3]=(node){x3,y3};h[4*i+4]=(node){x4,y4};for(int j=1;j&=4;j++)for(int k=1;k&=4;k++)dis[4*i+j][4*i+k]=tt*qjll(h[4*i+j], h[4*i+k]);}dis[0][0]=0;for(int i=1;i&=4;i++)dis[0][4*A-4+i]=0;for(int i=1;i&=4;i++)dis[4*A-4+i][0]=0;for(int i=1;i&=4*s;i++)for(int j=1;j&=4*s;j++)if((i-1)/4!=(j-1)/4)dis[i][j]=t*qjll(h[i],h[j]);for(int k=1;k&=4*s;k++)for(int i=0;i&=4*s;i++)for(int j=0;j&=4*s;j++)dis[i][j]=minnn(dis[i][k]+dis[k][j],dis[i][j]);double ans=minnn4(dis[0][4*B-4+1],dis[0][4*B-4+2],dis[0][4*B-4+3],dis[0][4*B-4+4]);printf("%.1lf\n",ans);}return 0;}
by 46611 十一月 2,
Solution_ID:22681& && && && &又水又烦
& && && && & & && &时间复杂度：Θ（H?O) 空间复杂度：Θ（H?O)
# include &stdio.h&# include &stdlib.h&# include &iostream&# include &string.h&# include &cmath&# include &queue&# define ll long long# define oo # define mem(a, b) memset(a, b, sizeof(a))int s, a, b, boo[101][5];double dist[101][5], ti[101],struct point{ double x,} c[101][5];struct node{ int x,};queue &node& Q;inline double dis(double x1, double y1, double x2, double y2, double cost){ return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) *}inline void copy(int i, int k1, int k2, int k3){ double dx = c[i][k1].x - c[i][k2].x, dy = c[i][k1].y - c[i][k2].y; c[i][4].x = c[i][k3].x + dx, c[i][4].y = c[i][k3].y +}inline void next(int i){ double k1, k2, k3; k1 = dis(c[i][1].x, c[i][1].y, c[i][2].x, c[i][2].y, 1); k2 = dis(c[i][1].x, c[i][1].y, c[i][3].x, c[i][3].y, 1); k3 = dis(c[i][3].x, c[i][3].y, c[i][2].x, c[i][2].y, 1); if(k3 & k2 && k3 & k1) copy(i, 2, 1, 3); if(k2 & k1 && k2 & k3) copy(i, 1, 2, 3); if(k1 & k2 && k1 & k3) copy(i, 1, 3, 2);}inline void spfa(){ boo[a][1] = boo[a][2] = boo[a][3] = boo[a][4] = 1; dist[a][1] = dist[a][2] = dist[a][3] = dist[a][4] = 0;
st.x = st.cnt = 1; Q.push(st); </t = 2; Q.push(st); st.cnt = 3; Q.push(st); st.cnt = 4; Q.push(st); while(!Q.empty()) {
node u = Q.front(); Q.pop(); boo[u.x][u.cnt] = 0;
for(int i = 1; i &= i++)
int cost = if(i == u.x) cost = ti[i];
for(int j = 1; j &= 4; j++)
double k = dis(c[u.x][u.cnt].x, c[u.x][u.cnt].y, c[i][j].x, c[i][j].y, cost);
if(dist[i][j] & dist[u.x][u.cnt] + k)
dist[i][j] = dist[u.x][u.cnt] +
if(!boo[i][j])
boo[i][j] = 1;
node v = {i, j};
Q.push(v);
} }}inline double min(int i){ double minn = for(int j = 1; j &= 4; j++)
if(dist[i][j] & minn) minn = dist[i][j]; }int main(){
scanf("%d", &n); while(n--) {
scanf("%d%lf%d%d", &s, &t, &a, &b);
for(int i = 1; i &= i++)
dist[i][1] = dist[i][2] = dist[i][3] = dist[i][4] =
for(int j = 1; j &= 3; j++) scanf("%lf%lf", &c[i][j].x, &c[i][j].y);
scanf("%lf", &ti[i]);
printf("%.1lf", min(b)); } return 0;}
by 30355 十月 28,
Solution_ID:22580& && && && &spfa
& && && && & & && &时间复杂度：Θ（o（100ns ^2左右）) 空间复杂度：Θ（)
n=4s每个机场看做一个点，并算出每两个点之间的距离（如果在同一个城市将会有两种算法）然后枚举一下开始的四个机场和结束的4个注意给出一个矩形的三个点求最后一个点可以用大角对大边的定理（即斜边大于直角边）
by 26949 十月 25,
Solution_ID:22178& && && && &Floyd
& && && && & & && &时间复杂度：Θ（（n^3)) 空间复杂度：Θ（)
#include&iostream&#include&cstdio&#include&vector&#include&cmath&struct node{int x,} h[500];double minnn(double x, double y){ if (x & y)}double qjl(int x1, int y1, int x2, int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double qjll(node a1, node a2) { return qjl(a1.x, a1.y, a2.x, a2.y);}double minnn4(double a, double b, double c, double d) { return minnn(minnn(a, b), minnn(c, d));}int main(){ scanf("%d", &o); for (int owo = 1; owo &= owo++) {
int s, t, A, B, tt = 0;
scanf("%d%d%d%d", &s, &t, &A, &B);
double dis[500][500];
for (int i = 0; i & 4*s+1; i++) for (int j = 0; j & 4*s+1; j++) dis[i][j] = 1e8;
for (int i = 0; i &= s-1; i++)
int x1, y11, x2, y2, x3, y3, x4, y4,
scanf("%d%d%d%d%d%d%d", &x1, &y11, &x2, &y2, &x3, &y3, &tt);
double g1 = qjl(x1, y11, x2, y2), g2 = qjl(x1, y11, x3, y3);
double g3 = qjl(x2, y2, x3, y3);
if (g2 &= g1 && g2 &= g3){ x4 = x3+x1-x2;
y4 = y3+y11-y2;}
if (g1 &= g2 && g1 &= g3){ x4 = x2+x1-x3;
y4 = y2+y11-y3;}
if (g3 &= g1 && g3 &= g2){ x4 = x3+x2-x1; y4 = y3+y2-y11;}
h[4*i+1] = (node){x1, y11};
h[4*i+2] = (node){x2, y2};
h[4*i+3] = (node){x3, y3};
h[4*i+4] = (node){x4, y4};
for (int j = 1; j &= 4; j++)
for (int k = 1; k &= 4; k++)
dis[4*i+j][4*i+k] = tt*qjll(h[4*i+j], h[4*i+k]);
dis[0][0] = 0;
for (int i = 1; i &= 4; i++) dis[0][4*A-4+i] = 0;
for (int i = 1; i &= 4; i++) dis[4*A-4+i][0] = 0;
for (int i = 1; i &= 4*s; i++)
for (int j = 1; j &= 4*s; j++)
if ((i-1)/4 != (j-1)/4) dis[i][j] = t*qjll(h[i], h[j]);
for (int k = 1; k &= 4*s; k++)
for (int i = 0; i &= 4*s; i++)
for (int j = 0; j &= 4*s; j++)
dis[i][j] = minnn(dis[i][k]+dis[k][j], dis[i][j]);
double ans = minnn4(dis[0][4*B-4+1], dis[0][4*B-4+2], dis[0][4*B-4+3], dis[0][4*B-4+4]);
printf("%.1lf\n", ans); } return 0;}
by 41317 十月 15,
Solution_ID:20940& && && && &绝对能看懂
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
http://blog.csdn.net/cax1165/article/details/
by 33475 八月 23,
Solution_ID:20578& && && && &不多说，上代码，简单粗暴好理解
& && && && & & && &时间复杂度：Θ（n^3) 空间复杂度：Θ（n)
#include &iostream&#include &stdio.h&#include &math.h&const int MAXN = 404 ;struct Node {int x,y,} node[MAXN];double pre[MAXN/4];int s,t,a,b;double com(Node a,Node b) {res=sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);if(a.city==b.city)return res*pre[a.city];return res*t;}int main () {int n,double map[MAXN][MAXN];scanf("%d",&n);for(casee=0; casee&n; casee++) {scanf("%d%d%d%d",&s,&t,&a,&b);int nodenum=0,ti,x1,x2,x3,x4,y1,y2,y3,y4;for(int i=1; i&=s; i++) {scanf("%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&ti);pre[i]=node[nodenum].x=x1;node[nodenum].y=y1;node[nodenum++].city=i;node[nodenum].x=x2;node[nodenum].y=y2;node[nodenum++].city=i;node[nodenum].x=x3;node[nodenum].y=y3;node[nodenum++].city=i;double l12=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));double l23=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));double l13=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));if(l12&l23&&l12&l13) {x4=x1+x2-x3;y4=y1+y2-y3;} else if(l23&l12&&l23&l13) {x4=x2+x3-x1;y4=y2+y3-y1;} else {x4=x1+x3-x2;y4=y1+y3-y2;}node[nodenum].x=x4;node[nodenum].y=y4;node[nodenum++].city=i;}for(int i=0; i& i++) {for(int j=0; j& j++) {map[i][j]=com(node[i],node[j]);}}double minn=9999999;for(int k=0; k& k++) {for(int i=0; i& i++) {for(int j=0; j& j++) {if(map[i][j]&map[i][k]+map[k][j]) {map[i][j]=map[i][k]+map[k][j];}}}}for(int i=0; i& i++) {for(int j=0; j& j++)if(node[i].city==a&&node[j].city==b)minn=min(map[i][j],minn);}if(minn==9999999)printf("0.0\n");elseprintf("%.1f\n",minn);}return 0;}
by 40029 八月 11,
Solution_ID:20250& && && && &这题太水，推荐一道好的最短路题
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
codevs 5172 这道题要动动脑筋，适合用于理解最短路算法原理的三角不等式。
by 36099 八月 2,
Solution_ID:20237& && && && &Eden
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
欢迎参加洛谷比赛：http://www.luogu.org/contest/show?tid=773本题题解：/eden_/blog/#m=0&t=3&c=codevs
by 21413 八月 1,
Solution_ID:19606& && && && &Eden
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
欢迎参加luogu比赛http://www.luogu.org/contest/show?tid=717 本题题解：/eden_/blog/static//
by 21413 七月 15,
Solution_ID:19058& && && && &这么暴力竟然过！发个题解纪念一下
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&cstdio&#include&iostream&#include&cstring&#include&cmath&#define M 410#define INF 9999999double x[M],y[M],map[M][M],t;int belong[M],n,A,B,tot=0;void get_four(int i,int zh){int r1=tot-2,r2=tot-1,r3=tot,map[r1][r2]=map[r2][r1]=pow(x[r1]-x[r2],2)+pow(y[r1]-y[r2],2);map[r1][r3]=map[r3][r1]=pow(x[r1]-x[r3],2)+pow(y[r1]-y[r3],2);map[r3][r2]=map[r2][r3]=pow(x[r3]-x[r2],2)+pow(y[r3]-y[r2],2);if(map[r1][r2]+map[r1][r3]==map[r2][r3])rr=r1;else if(map[r1][r2]+map[r2][r3]==map[r1][r3])rr=r2;else rr=r3;tot++;if(rr==r1){double xx=x[r1]-x[r2],yy=y[r1]-y[r2];x[tot]=x[r3]-y[tot]=y[r3]-}if(rr==r2){double xx=x[r1]-x[r2],yy=y[r1]-y[r2];x[tot]=x[r3]+y[tot]=y[r3]+}if(rr==r3){double xx=x[r1]-x[r3],yy=y[r1]-y[r3];x[tot]=x[r2]+y[tot]=y[r2]+}for(int j=tot-3;j&=j++)
for(int k=tot-3;k&j;k++)
map[j][k]=map[k][j]=sqrt(pow(x[j]-x[k],2)+pow(y[j]-y[k],2))*belong[tot]=i;}void floyed(){for(int k=1;k&=k++)
for(int i=1;i&=i++)
for(int j=1;j&=j++)
if(i!=j&&i!=k&&j!=k)
map[i][j]=min(map[i][k]+map[k][j],map[i][j]);double ans=INF; for(int i=1;i&=i++)
for(int j=1;j&=j++)
if(belong[i]==A&&belong[j]==B)
ans=min(map[i][j],ans);printf("%.1lf\n",ans);}void work(){scanf("%d%lf%d%d",&n,&t,&A,&B);for(int i=1;i&=n;i++){for(int j=1;j&=3;j++){tot++;scanf("%lf%lf",&x[tot],&y[tot]);belong[tot]=i;}scanf("%d",&x);get_four(i,x);}for(int i=1;i&=i++)
for(int j=1;j&i;j++)
if(belong[i]!=belong[j])
map[i][j]=map[j][i]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2))*t;floyed();}int main(){freopen("jh.in","r",stdin);int T;scanf("%d",&T);while(T--){memset(map,0,sizeof(map));memset(x,0,sizeof(x));memset(y,0,sizeof(y));memset(belong,0,sizeof(belong));work();}return 0;}
by 35543 六月 29,
Solution_ID:18731& && && && &测试数据
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
数据太水了！！！！！！！！！！！！！！！！！！！！！！数据太水了！！！！！！！！！！！！！！！！！！！！！！数据太水了！！！！！！！！！！！！！！！！！！！！！！所有数据ｎ=1,s&20,根本测不出差异；我用spfa和floyd时间都是一样提供一份自己生成的数据，供大家调试用输入：10100 52 23 74752 59 752 963 722 59 69521 790 521 282 820 790 94526 912 526 887 487 912 83683 985 683 469 502 985 48162 93 162 399 807 93 22647 982 647 794 651 982 47536 188 536 919 455 188 78104 317 104 373 47 317 21486 808 486 551 376 808 69964 138 964 199 225 138 15932 632 932 760 223 632 1859 219 59 703 936 219 95904 982 904 631 646 982 39264 382 264 141 61 382 582 680 2 681 727 680 48913 940 913 188 56 940 31344 159 344 539 837 159 38633 47 633 336 378 47 52797 809 797 874 21 809 12970 74 970 24 382 74 18119 853 119 855 328 853 6994 391 94 540 813 391 82855 476 855 261 975 476 937 493 37 211 573 493 12506 948 506 284 443 948 52949 180 949 931 900 180 18700 750 700 209 255 750 58472 834 472 205 641 834 4346 925 46 586 782 925 921 660 1 319 67 660 24135 554 135 439 732 554 39111 341 111 537 734 341 95837 90 837 529 498 90 58291 953 291 79 459 953 26871 916 871 895 977 916 8988 321 988 541 562 321 92624 446 624 883 428 446 3530 411 530 222 356 411 96509 133 509 881 4 133 34253 24 253 864 502 24 77946 379 946 1 482 379 15856 950 856 507 459 950 80421 262 421 214 909 262 75196 202 196 905 894 202 34123 803 123 9 200 803 691 908 91 995 845 908 28555 829 555 705 568 829 23772 139 772 845 589 139 40384 919 384 134 880 919 41149 452 149 965 856 452 32687 189 687 729 51 189 51553 438 553 419 254 438 85891 262 891 216 188 262 18752 55 752 584 707 55 63172 414 172 172 897 414 88496 338 496 86 482 338 49959 167 959 914 643 167 79100 102 100 246 101 102 96702 131 702 539 924 131 37440 846 440 760 228 846 87241 332 241 656 908 332 92672 118 672 978 624 118 4117 218 117 500 712 218 98736 464 736 752 608 464 98174 616 174 854 265 616 69795 689 795 833 206 689 32798 755 798 656 430 755 77927 793 927 81 591 793 35448 749 448 417 199 749 50146 573 146 659 423 573 21663 145 663 809 157 145 59862 799 862 810 617 799 27797 90 797 93 494 90 39844 57 844 165 934 57 86322 801 322 512 344 801 21174 12 174 565 660 12 75882 97 882 679 738 97 19284 79 284 683 821 79 30385 318 385 187 601 318 72513 448 513 891 794 448 97551 674 551 614 661 674 5370 143 370 533 117 143 96491 530 491 585 424 530 84445 540 445 601 759 540 64261 37 261 4 188 37 97311 575 311 395 312 575 2968 350 68 878 62 350 5427 839 427 777 592 839 32932 263 932 596 641 263 80619 131 619 601 98 131 61359 817 359 153 148 817 26755 790 755 580 822 790 8730 178 30 744 967 178 17491 503 491 751 165 503 92748 237 748 601 261 237 78901 352 901 516 293 352 19146 738 146 886 430 738 5201 745 201 549 295 745 67917 846 917 174 83 846 46139 738 139 328 115 738 43100 86 28 78641 302 641 682 157 302 28559 353 559 865 877 353 99294 627 294 870 76 627 16796 755 796 181 766 755 59358 848 358 950 654 848 84893 847 893 316 453 847 29868 821 868 547 243 821 1580 914 80 295 774 914 16946 982 946 508 153 982 67828 396 828 554 216 396 17933 865 933 616 685 865 12520 705 520 995 227 705 81915 345 915 417 9 345 62663 200 663 212 76 200 96830 282 830 363 482 282 51314 549 314 475 689 549 93429 26 429 160 29 26 98851 364 851 50 17 364 43556 609 556 98 445 609 18448 200 448 833 266 200 49210 488 210 979 101 488 74900 350 900 243 339 350 70220 642 220 550 527 642 33662 970 662 41 827 970 1722 626 722 824 965 626 43545 565 545 228 256 565 5693 130 693 912 337 130 8281 360 281 668 963 360 3558 734 58 581 151 734 38492 264 492 623 259 264 4880 956 80 418 24 956 93439 514 439 132 345 514 21432 663 432 731 634 663 93502 416 502 261 138 416 25204 337 204 871 319 337 76724 413 724 770 642 413 5678 940 678 96 215 940 36109 683 109 866 80 683 22726 72 726 23 20 72 53781 184 781 508 649 184 26665 155 665 831 173 155 10739 183 739 403 745 183 2480 370 80 213 697 370 25899 468 899 395 790 468 3633 364 33 314 220 364 97523 175 523 633 726 175 41867 291 867 179 898 291 50117 229 117 810 635 229 1165 821 165 96 279 821 0578 341 578 904 303 341 42869 326 869 430 636 326 12878 910 878 599 612 910 53783 795 783 558 129 795 5745 808 45 708 887 808 87339 155 339 110 446 155 11764 358 764 936 547 358 9091 773 91 444 436 773 48650 566 650 40 78 566 70724 106 724 731 783 106 61342 413 342 186 204 413 76867 810 867 917 218 810 6694 452 94 89 723 452 65470 355 470 715 48 355 94652 565 652 547 471 565 48404 332 404 292 257 332 1023 343 23 278 896 343 9482 388 82 117 25 388 39369 594 369 768 357 594 79713 148 713 115 495 148 71888 709 888 216 198 709 069 767 69 465 0 767 0172 590 172 695 445 590 6891 970 891 730 961 970 74456 210 456 557 286 210 50964 723 964 95 364 723 89343 273 343 961 977 273 6565 215 65 997 228 215 49261 455 261 320 37 455 5138 612 38 920 951 612 34146 998 146 575 198 998 51808 374 808 321 970 374 79780 617 780 699 251 617 96899 760 899 4 926 760 29988 376 988 699 145 376 44446 717 446 639 610 717 16604 24 604 888 306 24 38609 740 609 877 472 740 38928 891 928 405 514 891 14151 641 151 529 629 641 1400 418 400 949 660 418 92479 592 479 976 85 592 17530 448 530 675 781 448 41235 409 235 93 538 409 86929 5 929 269 621 5 78211 41 211 135 742 41 82624 233 624 434 217 233 79547 593 547 771 58 593 94922 980 922 626 272 980 94528 227 528 516 721 227 71980 803 980 909 957 803 94100 37 48 87533 23 533 66 666 23 39980 360 980 956 983 360 89371 239 371 442 814 239 6790 933 790 779 216 933 8120 33 120 913 925 33 91376 601 376 911 193 601 70595 555 595 546 288 555 43813 865 813 714 37 865 30766 216 766 972 10 216 61220 882 220 752 266 882 77338 180 338 161 827 180 11610 991 610 925 232 991 44523 322 523 772 492 322 7862 714 62 951 249 714 5856 331 856 169 681 331 13113 739 113 943 273 739 41222 712 222 179 446 712 7096 970 96 41 613 970 4556 40 56 734 78 40 17808 740 808 132 784 740 6639 779 39 742 523 779 99118 628 118 488 245 628 92669 737 669 179 712 737 64420 370 420 194 683 370 90985 606 985 358 92 606 90993 992 993 164 677 992 94565 450 565 5 816 450 14765 844 765 7 256 844 97853 255 853 32 81 255 29545 667 545 550 84 667 63967 285 967 85 702 285 45896 387 896 243 959 387 62647 593 647 9 701 593 20256 61 256 350 77 61 48852 334 852 561 192 334 85219 515 219 639 215 515 1837 71 37 74 685 71 67706 703 706 655 827 703 15333 670 333 482 839 670 9726 967 726 342 996 967 97847 358 847 279 212 358 65143 164 143 324 557 164 7284 590 284 703 340 590 784 297 4 241 474 297 47145 224 145 903 172 224 7993 842 93 734 913 842 472 753 2 89 66 753 43174 686 174 672 514 686 98925 601 925 904 921 601 84415 419 415 552 274 419 58183 384 183 543 84 384 99418 977 418 424 289 977 84940 213 940 659 189 213 51721 244 721 689 506 244 50991 176 991 904 608 176 13253 490 253 432 815 490 4712 678 712 271 291 678 50537 451 537 99 206 451 55512 79 512 227 268 79 7204 623 204 86 667 623 13237 505 237 216 306 505 55149 63 149 562 968 63 68352 600 352 495 109 600 2131 794 31 538 665 794 31437 871 437 618 370 871 23510 897 510 122 687 897 58692 789 692 284 719 789 33171 738 171 935 817 738 73876 609 876 937 749 609 29126 514 126 336 457 514 20550 568 550 408 407 568 74551 701 551 964 293 701 67767 284 767 341 842 284 33332 34 332 978 68 34 33548 547 548 96 822 547 0424 552 424 635 710 552 84823 789 823 552 770 789 63856 63 856 366 652 63 81969 995 969 700 926 995 66387 354 387 691 522 354 34960 359 960 441 709 359 7978 536 78 966 502 536 19369 114 369 499 731 114 64236 426 236 569 772 426 46391 393 391 162 631 393 10897 746 897 425 596 746 29541 279 541 602 696 279 71818 408 818 294 22 408 12155 25 155 90 587 25 37604 347 604 691 854 347 55104 398 104 503 201 398 63530 392 530 241 701 392 86587 810 587 369 219 810 96677 607 677 381 670 607 54498 41 498 303 997 41 50627 623 627 147 691 623 26784 466 784 321 631 466 85885 692 885 48 735 692 66674 509 674 142 43 509 80993 812 993 292 407 812 81100 58 2 76285 520 285 641 269 520 50695 251 695 250 486 251 86631 718 631 529 594 718 25158 947 158 101 513 947 8488 352 88 968 200 352 84666 188 666 420 435 188 44209 207 209 818 159 207 1481 378 81 324 966 378 12304 509 304 21 620 509 36148 271 148 395 395 271 23812 416 812 222 591 416 71410 404 410 847 668 404 98473 810 473 553 162 810 1358 345 358 662 339 345 52496 958 496 64 935 958 26384 326 384 229 54 326 29967 665 967 229 633 665 44516 557 516 839 736 557 45692 482 692 60 540 482 78549 645 549 33 744 645 76368 595 368 205 905 595 52126 660 126 397 489 660 82880 279 880 644 697 279 8764 190 764 63 945 190 41293 358 293 874 307 358 23763 750 763 57 900 750 88497 187 497 356 111 187 60666 833 666 850 138 833 8851 217 851 180 303 217 81422 373 422 110 806 373 45471 606 471 940 226 606 48898 945 898 894 467 945 90366 386 366 412 733 386 10932 382 932 470 568 382 65304 882 304 309 951 882 54854 264 854 708 724 264 0541 177 541 887 401 177 94496 457 496 719 41 457 6298 849 98 42 806 849 95258 303 258 197 355 303 7700 883 700 414 285 883 66865 711 865 946 200 711 20434 817 434 552 23 817 10325 986 325 390 371 986 27281 937 281 968 167 937 32183 259 183 640 575 259 32514 770 514 607 636 770 37802 643 802 74 588 643 13226 356 226 456 937 356 9051 179 51 434 143 179 91468 77 468 329 83 77 55673 34 673 342 92 34 79432 26 432 3 378 26 7809 769 809 978 846 769 97229 483 229 354 365 483 39793 559 793 604 341 559 31907 844 907 645 702 844 75601 490 601 713 375 490 88894 655 894 295 276 655 12251 295 251 80 809 295 38803 253 803 847 616 253 0229 521 229 844 398 521 30965 90 965 170 754 90 45735 39 735 312 570 39 16973 203 973 758 204 203 49343 321 343 275 865 321 90378 637 378 945 862 637 81672 993 672 727 749 993 58202 61 202 583 405 61 23988 106 988 798 560 106 31740 431 740 854 458 431 43445 263 445 773 217 263 86789 517 789 16 365 517 6045 651 45 324 560 651 41656 521 656 658 58 521 88441 809 441 674 465 809 54610 997 610 104 455 997 45602 317 602 412 742 317 39576 962 576 478 940 962 91240 30 240 326 43 30 77340 633 340 475 220 633 36765 719 765 910 5 719 7253 662 53 383 16 662 92705 611 705 362 479 611 17979 310 979 322 51 310 74973 924 973 963 365 924 50828 761 828 374 502 761 9258 809 258 930 85 809 5343 822 343 49 863 822 98319 609 319 182 572 609 25632 831 632 928 917 831 53138 823 138 196 552 823 26667 675 667 999 550 675 11922 63 922 252 410 63 58143 657 143 749 447 657 28896 413 896 131 740 413 41991 561 991 151 511 561 44884 452 884 763 332 452 97959 912 959 895 196 912 70939 413 939 577 577 413 84100 47 1 6013 556 13 849 255 556 54593 959 593 42 480 959 92365 64 365 376 303 64 16466 998 466 308 447 998 96694 919 694 717 262 919 25535 931 535 498 718 931 22887 746 887 965 501 746 6103 605 103 341 592 605 40959 839 959 518 57 839 61168 987 168 126 446 987 19543 43 543 439 511 43 16123 367 123 147 229 367 33576 788 576 4 389 788 88730 905 730 632 931 905 38100 856 100 983 606 856 65473 464 473 620 872 464 13241 842 241 967 325 842 0351 757 351 911 658 757 32498 267 498 160 190 267 54921 659 921 794 971 659 30391 356 391 833 608 356 20502 195 502 310 166 195 14614 361 614 48 500 361 20600 273 600 26 978 273 4054 548 54 545 112 548 23371 944 371 279 731 944 64640 230 640 889 795 230 428 827 8 212 335 827 2212 131 12 290 816 131 6831 532 831 309 169 532 2602 527 602 9 704 527 96356 617 356 175 923 617 5660 661 60 71 184 661 35147 783 147 567 555 783 8255 520 55 318 877 520 25675 16 675 902 992 16 55642 756 642 685 374 756 5186 114 86 137 127 114 35480 18 480 138 597 18 20595 767 595 764 108 767 95645 838 645 117 171 838 43587 161 587 269 163 161 18418 90 418 673 514 90 56189 73 189 394 157 73 25632 559 632 895 58 559 99634 763 634 546 111 763 90875 984 875 880 154 984 6798 740 798 369 916 740 8297 560 297 422 329 560 27514 845 514 371 746 845 7323 149 23 29 359 149 72247 172 247 356 250 172 77420 731 420 840 643 731 5781 215 81 682 647 215 24728 765 728 737 312 765 39340 492 340 873 436 492 47108 614 108 425 940 614 24219 827 219 306 771 827 74948 688 948 752 316 688 463 569 63 335 679 569 75598 122 598 80 109 122 33133 524 133 849 400 524 61514 222 514 270 957 222 86385 237 385 517 312 237 11407 209 407 925 328 209 20635 798 635 536 245 798 3340 616 340 67 843 616 7371 482 71 120 752 482 23105 670 105 538 473 670 8786 603 86 907 996 603 53589 696 589 227 537 696 2408 885 408 572 712 885 51508 713 508 867 507 713 55137 744 137 764 86 744 77821 537 821 746 875 537 25257 93 257 732 713 93 58542 454 542 346 250 454 91940 881 940 293 961 881 91664 587 664 797 298 587 70335 610 335 647 430 610 45596 17 596 251 448 17 49970 672 970 756 632 672 328 140 28 928 375 140 55121 679 121 31 899 679 0613 363 613 819 529 363 8133 90 133 660 788 90 91403 567 403 990 154 567 34318 542 318 606 108 542 30725 526 725 169 973 526 23297 452 297 809 266 452 83269 221 269 57 514 221 62251 863 251 964 28 863 69692 404 692 553 683 404 77912 172 912 152 129 172 33144 405 144 140 167 405 53125 581 125 125 581 581 97949 766 949 965 277 766 54877 795 877 826 173 795 94312 327 312 952 465 327 5538 995 538 419 608 995 61100 51 31 82701 175 701 311 318 175 29109 673 109 748 429 673 53668 738 668 163 342 738 86349 482 349 577 629 482 5171 230 71 367 349 230 2219 211 219 291 23 211 99834 762 834 2 659 762 71472 848 472 996 659 848 4147 360 147 774 125 360 52770 805 770 571 605 805 16987 994 987 119 217 994 28181 192 181 550 231 192 64352 895 352 242 920 895 27952 557 952 746 790 557 45709 854 709 253 293 854 73440 666 440 167 916 666 3736 575 736 389 883 575 31638 287 638 563 246 287 62825 883 825 232 571 883 2831 625 831 948 403 625 66795 715 795 354 822 715 3734 589 734 780 545 589 90334 579 334 572 953 579 61100 147 100 248 368 147 78548 602 548 748 985 602 95410 276 410 487 344 276 6236 542 236 189 56 542 3889 924 889 613 805 924 2779 389 779 99 348 389 96991 839 991 343 781 839 83415 438 415 616 184 438 16722 455 722 833 981 455 16856 267 856 443 461 267 95777 86 777 272 524 86 39243 830 243 639 51 830 15750 932 750 910 661 932 924 211 24 227 368 211 12598 629 598 645 341 629 2840 403 40 752 30 403 81294 728 294 212 768 728 47584 67 584 173 640 67 5358 357 358 481 632 357 4675 608 75 343 231 608 50719 901 719 601 126 901 8865 260 865 259 53 260 77376 559 376 692 809 559 72233 267 233 14 159 267 27676 603 676 809 459 603 51390 925 390 483 934 925 86773 861 773 912 935 861 4832 155 32 941 259 155 34225 824 225 851 273 824 8146 711 146 545 720 711 87726 617 726 940 533 617 93128 113 128 684 117 113 69893 356 893 749 809 356 65369 70 369 131 748 70 13831 926 831 318 959 926 53971 697 971 348 599 697 67176 394 176 355 703 394 21738 283 738 933 809 283 15383 921 383 88 267 921 10771 916 771 502 709 916 61539 676 539 550 516 676 1392 38 392 72 514 38 67845 489 845 256 943 489 16422 74 422 771 458 74 35425 579 425 597 789 579 90684 801 684 77 975 801 78288 81 288 984 442 81 2547 262 547 492 502 262 40315 56 315 940 779 56 8657 804 57 75 855 804 8478 767 78 60 919 767 16323 518 323 356 858 518 96373 840 373 220 535 840 32971 890 971 356 314 890 78602 186 602 659 60 186 40228 197 228 426 454 197 37691 814 691 795 468 814 9273 34 273 958 868 34 68305 562 305 938 425 562 45387 570 387 456 818 570 18690 952 690 540 67 952 88921 789 921 432 712 789 89826 420 826 490 212 420 29651 201 651 901 665 201 53686 738 686 212 929 738 77468 464 468 452 530 464 74508 185 508 194 832 185 586 111 86 529 679 111 88162 469 162 165 744 469 94212 295 212 417 314 295 2163 296 63 484 226 296 6716 283 16 48 262 283 95782 353 782 691 407 353 91420 406 420 693 241 406 42688 7 688 578 303 7 24270 522 270 649 541 522 77663 801 663 760 898 801 55100 52 41 84125 403 125 388 524 403 68433 131 433 815 207 131 86399 743 399 958 820 743 4698 271 98 714 373 271 32480 14 480 812 636 14 75374 819 374 398 971 819 66830 691 830 255 925 691 91195 394 195 806 622 394 27730 475 730 361 498 475 72564 677 564 382 834 677 17384 659 384 851 452 659 91825 379 825 824 836 379 26588 327 588 873 717 327 90162 440 162 409 823 440 94989 562 989 408 713 562 15626 788 626 172 42 788 98142 303 142 647 406 303 45768 698 768 67 603 698 19936 362 936 41 859 362 18338 598 338 822 103 598 1681 989 681 89 355 989 45198 164 198 203 173 164 81297 933 297 351 893 933 6120 878 120 419 26 878 99779 676 779 778 973 676 74257 13 257 39 121 13 76566 264 566 458 718 264 81240 356 240 706 320 356 70688 319 688 212 170 319 89880 61 880 760 509 61 52807 148 807 539 629 148 55781 906 781 175 651 906 21555 8 555 28 821 8 42576 71 576 710 889 71 1675 28 75 923 167 28 59538 496 538 361 605 496 68504 849 504 974 972 849 79561 972 561 875 497 972 92414 150 414 258 726 150 21749 620 749 665 823 620 16106 674 106 415 458 674 24498 263 498 787 150 263 58187 672 187 803 827 672 49819 745 819 139 296 745 75280 474 280 651 60 474 87250 386 250 523 886 386 7447 905 47 343 467 905 85695 813 695 107 95 813 57139 967 139 833 892 967 12541 362 541 946 861 362 18302 314 302 799 444 314 7450 314 50 65 333 314 2833 216 833 756 147 216 21948 444 948 847 552 444 44984 459 984 25 66 459 9928 983 928 731 610 983 51902 677 902 307 870 677 37115 97 115 137 790 97 81375 529 375 854 157 529 996 622 6 674 762 622 42181 621 181 856 915 621 65605 69 605 769 651 69 79295 607 295 906 752 607 15136 116 136 424 161 116 24783 300 783 367 739 300 12292 837 292 505 741 837 35919 345 919 192 398 345 66316 138 316 461 365 138 80199 782 199 510 188 782 19699 219 699 232 906 219 96407 196 407 57 473 196 69748 600 748 999 392 600 5732 869 32 557 936 869 86196 411 196 942 897 411 66135 850 135 474 405 850 37144 362 144 967 410 362 68412 976 412 340 730 976 65446 265 446 60 18 265 31796 52 796 238 232 52 84925 254 925 91 106 254 98611 413 611 61 99 413 1029 48 29 264 297 48 16166 432 166 83 373 432 49487 915 487 488 533 915 58898 940 898 219 678 940 38631 499 631 451 202 499 81803 530 803 249 44 530 35170 496 170 676 709 496 24161 37 161 457 811 37 14712 444 712 13 434 444 2474 644 474 540 217 644 86102 765 102 403 743 765 5326 762 326 587 585 762 665 757 65 82 844 757 2577 689 577 398 514 689 78567 621 567 212 781 621 76108 631 108 597 955 631 2154 953 154 879 975 953 4348 690 348 31 972 690 5755 576 55 131 547 576 26100 11 20 94102 735 102 665 178 735 85290 744 290 138 94 744 1048 942 48 648 215 942 41759 470 759 877 199 470 61709 497 709 147 905 497 75607 59 607 527 539 59 7809 950 809 900 178 950 71206 233 206 732 839 233 17274 881 274 167 80 881 25754 315 754 573 242 315 62681 364 681 874 689 364 64760 396 760 246 820 396 3156 242 156 886 44 242 4015 57 15 960 665 57 29682 589 682 475 166 589 3115 730 115 69 832 730 72470 632 470 451 965 632 35353 481 353 348 611 481 86539 943 539 756 941 943 93521 838 521 817 225 838 6524 128 524 116 100 128 77977 865 977 680 408 865 36596 557 596 333 623 557 62306 724 306 15 325 724 90929 130 929 502 646 130 38266 925 266 753 338 925 43919 687 919 587 137 687 63463 158 463 610 11 158 9449 627 49 895 472 627 91585 489 585 812 963 489 98502 709 502 788 966 709 1477 514 77 97 460 514 14942 997 942 992 505 997 324 404 24 466 516 404 64992 595 992 811 627 595 67885 215 885 791 464 215 43460 346 460 996 55 346 53595 71 595 697 993 71 9816 128 816 595 921 128 45743 466 743 269 224 466 92645 931 645 484 868 931 26915 528 915 245 125 528 79143 662 143 6 974 662 44279 410 279 517 26 410 5097 692 97 922 171 692 15900 472 900 151 868 472 13564 691 564 249 618 691 31520 375 520 821 717 375 3453 430 453 269 510 430 80520 146 520 744 580 146 51920 11 920 501 119 11 36772 366 772 910 368 366 1647 656 647 550 643 656 93124 475 124 842 529 475 45153 765 153 909 816 765 74527 454 527 416 49 454 84103 642 103 818 286 642 28377 373 377 457 905 373 20622 141 622 612 664 141 95692 227 692 150 104 227 65509 719 509 404 983 719 11348 621 348 791 973 621 87761 16 761 950 249 16 94912 946 912 249 856 946 78338 331 338 867 882 331 97761 227 761 782 538 227 68502 310 502 507 281 310 69262 582 262 706 118 582 91777 894 777 547 707 894 99959 665 959 7 371 665 30362 355 362 143 101 355 89110 365 110 334 448 365 88200 983 200 124 694 983 12598 906 598 210 753 906 85603 38 603 692 250 38 32411 21 411 676 525 21 22862 881 862 101 781 881 70618 655 618 234 801 655 54369 7 369 448 600 7 58220 354 220 910 577 354 46960 22 960 600 835 22 94499 676 499 648 714 676 58210 734 210 128 117 734 93719 305 719 263 249 305 19722 354 722 394 184 354 42361 644 361 837 618 644 23899 694 899 446 744 694 79509 180 509 981 829 180 97669 161 669 567 260 161 28917 396 917 854 147 396 70937 456 937 965 480 456 58485 170 485 373 233 170 2729 370 729 723 600 370 35820 19 820 798 434 19 81674 961 674 385 146 961 5941 843 41 972 651 843 90330 874 330 136 24 874 77438 657 438 7 644 657 2431 780 431 909 900 780 55914 751 914 336 272 751 96100 15 45 87235 270 235 574 458 270 85738 755 738 538 610 755 8610 419 10 430 815 419 51986 882 986 705 993 882 47656 789 656 187 557 789 39588 657 588 704 814 657 20934 276 934 438 636 276 75466 999 466 299 519 999 54757 658 757 616 513 658 73132 797 132 600 270 797 11225 752 225 721 404 752 37549 848 549 735 432 848 62669 846 669 365 93 846 24702 284 702 91 319 284 26297 827 297 153 538 827 48305 542 305 196 128 542 18364 556 364 956 818 556 57194 386 194 4 88 386 96590 485 590 392 741 485 44719 369 719 594 33 369 96181 779 181 907 178 779 63228 671 228 835 970 671 87147 82 147 388 597 82 70375 357 375 8 929 357 5975 962 975 340 917 962 37966 193 966 326 546 193 34160 860 160 484 394 860 9461 86 61 363 541 86 30678 454 678 270 292 454 59725 255 725 286 727 255 10492 486 492 397 307 486 17692 542 692 2 426 542 73546 885 546 99 726 885 6567 787 67 591 399 787 48720 56 720 854 609 56 69467 277 467 331 697 277 56884 132 884 342 744 132 27495 865 495 743 346 865 73730 441 730 173 67 441 57655 668 655 161 595 668 54513 26 513 124 611 26 22434 408 434 919 746 408 71385 396 385 556 168 396 53927 553 927 925 467 553 15774 463 774 476 572 463 26637 573 637 901 5 573 44309 335 309 393 352 335 94632 26 632 425 164 26 61354 74 354 959 99 74 0683 888 683 793 220 888 90315 178 315 342 881 178 81926 671 926 253 386 671 87694 97 694 651 61 97 3717 662 717 941 55 662 48505 177 505 479 523 177 33165 11 165 554 27 11 75286 634 286 26 207 634 995 678 95 955 301 678 47572 130 572 291 697 130 12459 473 459 285 29 473 51621 919 621 757 887 919 5376 730 76 235 906 730 6342 875 342 795 241 875 49802 621 802 618 782 621 7678 777 78 975 399 777 88236 12 236 925 762 12 1286 496 86 567 446 496 2678 961 678 656 613 961 11539 917 539 8 885 917 82748 907 748 675 23 907 36620 124 620 961 530 124 71555 91 555 107 381 91 51994 218 994 151 169 218 27187 192 187 144 234 192 9754 743 754 294 198 743 98164 477 164 83 716 477 69945 670 945 471 448 670 9317 206 17 632 61 206 1179 929 79 292 443 929 82981 641 981 669 928 641 53858 114 858 199 248 114 8415 997 415 748 895 997 8666 889 666 559 253 889 39815 30 815 426 127 30 81475 456 475 732 542 456 80591 995 591 539 115 995 82680 749 680 369 368 749 27892 363 892 479 578 363 33245 489 245 780 438 489 57256 221 256 957 290 221 85449 462 449 546 755 462 75372 729 372 356 818 729 60662 998 662 679 353 998 33399 593 399 98 102 593 7021 266 21 728 952 266 36680 216 680 220 579 216 26800 290 800 421 64 290 129 327 29 99 270 327 34741 85 741 784 930 85 93562 356 562 662 39 356 44100 81 41 70556 576 556 25 994 576 11261 97 261 868 781 97 67652 573 652 283 162 573 70431 54 431 678 55 54 4861 514 61 777 240 514 2460 514 60 787 677 514 53949 605 949 863 51 605 17547 378 547 4 241 378 27209 62 209 749 717 62 93788 608 788 816 231 608 23911 71 911 760 415 71 9169 945 169 110 223 945 28679 834 679 629 251 834 50449 754 449 167 292 754 27414 751 414 906 136 751 30947 987 947 231 985 987 1274 242 274 230 773 242 56582 854 582 75 834 854 19960 277 960 503 823 277 80773 463 773 93 51 463 28814 432 814 786 55 432 88106 930 106 636 570 930 36477 350 477 487 49 350 23167 21 167 642 420 21 9758 48 758 804 768 48 35131 814 131 378 361 814 34242 604 242 63 370 604 92708 817 708 212 171 817 44966 576 966 137 911 576 8224 69 24 102 822 69 75573 146 573 217 414 146 7457 592 57 923 421 592 5489 583 489 411 123 583 31511 825 511 19 29 825 72461 295 461 615 808 295 42578 916 578 573 763 916 71822 599 822 496 926 599 3685 657 85 722 738 657 89784 565 784 790 235 565 55112 4 112 809 861 4 7502 944 502 143 421 944 11519 190 519 12 19 190 12263 406 263 33 406 406 78916 11 916 876 354 11 62464 281 464 468 467 281 86749 563 749 125 715 563 75829 751 829 876 207 751 46316 212 316 701 718 212 6567 158 67 424 883 158 61922 421 922 376 624 421 63534 894 534 600 832 894 4489 969 89 606 249 969 99195 350 195 931 694 350 44875 592 875 760 820 592 88679 721 679 643 158 721 0117 904 117 431 822 904 34327 249 327 805 962 249 13841 98 841 543 15 98 31322 846 322 342 158 846 77339 164 339 345 578 164 813 113 3 156 222 113 98658 661 658 366 366 661 74791 656 791 899 622 656 68528 208 528 131 209 208 72571 433 571 398 68 433 21253 360 253 899 637 360 4395 825 395 981 986 825 63939 0 939 217 972 0 16640 211 640 543 905 211 77699 596 699 575 122 596 5971 306 971 863 523 306 0342 26 342 246 118 26 37129 430 129 919 414 430 13616 17 616 438 229 17 42413 342 413 518 704 342 70480 50 480 454 865 50 36330 492 330 981 746 492 77195 563 195 629 145 563 27868 529 868 560 993 529 93486 987 486 655 596 987 6887 908 887 366 990 908 94631 289 631 550 469 289 89727 455 727 444 863 455 24281 833 281 87 418 833 1798 23 98 843 934 23 50253 116 253 230 238 116 2883 950 83 839 316 950 12492 31 492 932 745 31 6439 50 439 324 660 50 23113 171 113 930 241 171 87809 487 809 566 684 487 67923 201 923 762 72 201 11731 211 731 591 1 211 60336 872 336 514 30 872 7907 745 907 19 995 745 7094 618 94 719 577 618 49848 242 848 884 386 242 38999 416 999 616 533 416 10298 883 298 468 684 883 63909 365 909 682 723 365 99输出：5024.73846.02776.011716.32428.12800.84084.6979.61994.09435.9
by 34629 六月 5,
Solution_ID:18713& && && && &水题
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
虽然水，但我还是调了很久。。。细节决定成败啊！拆点，连起来，最短路（我直接暴力floyd）请叫我压行大神#include&cstdio&#include&cmath&#include&cstring&int x[401],y[401],c[401],n,cost,s,e;float f[401][401];int dis3(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}void pjy_dabendan(int k)//哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈{
int x1=x[k+1],x2=x[k+2],x3=x[k+3],y1=y[k+1],y2=y[k+2],y3=y[k+3];
int d1=dis3(x1,y1,x2,y2),d2=dis3(x1,y1,x3,y3),d3=dis3(x2,y2,x3,y3);
if (d1==d2+d3) {x[k+4]=x1+x2-x3; y[k+4]=y1+y2-y3;}
if (d2==d1+d3) {x[k+4]=x1+x3-x2; y[k+4]=y1+y3-y2;}
if (d3==d1+d2) {x[k+4]=x2+x3-x1; y[k+4]=y2+y3-y1;}}void dis(int i,int j){int cc=i/4;f[i][j]=f[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))*c[cc];}void dis2(int i,int j){f[i][j]=f[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))*}int main(){
scanf("%d",&ljj);
while (ljj--)
scanf("%d%d%d%d",&n,&cost,&s,&e);
for (int i=0;i&n;i++)
scanf("%d%d%d%d%d%d%d",&x[4*i+1],&y[4*i+1],&x[4*i+2],&y[4*i+2],&x[4*i+3],&y[4*i+3],&c[i]);
pjy_dabendan(4*i);
for (int i=0;i&n;i++)
int k=i*4;
dis(k+1,k+2); dis(k+1,k+3); dis(k+1,k+4); dis(k+2,k+3); dis(k+2,k+4); dis(k+3,k+4);
for (int i=1;i&=n-4;i++)
for (int j=i+1;j&=n;j++)
if ((i-1)/4!=(j-1)/4)
dis2(i,j);
for (int i=1;i&=n;i++)
f[i][i]=0;
for (int k=1;k&=n;k++)
for (int i=1;i&=n;i++)
for (int j=1;j&=n;j++)
if (i!=j&&i!=k&&j!=k&&f[i][k]+f[k][j]&f[i][j])
f[i][j]=f[i][k]+f[k][j];
float ans=;
for (int i=1;i&=4;i++)
for (int j=1;j&=4;j++)
if (f[4*(e-1)+i][4*(s-1)+j]&ans)
ans=f[4*(e-1)+i][4*(s-1)+j];
printf("%.1f\n",ans);
return 0;}
by 22234 六月 4,
Solution_ID:17161& && && && &短小精悍
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include &stdio.h&#include &iostream&struct node{ int name, node*};void insert(node *a, node *b){ node *c = while (c-&next != 0 && c-&next-&len & a-&len)
c = c-& a-&next = c-& c-&next =}int main(){ int n, scanf("%d", &n); int** len = new int*[n]; int *g = new int[n] {}; for (int i = 0; i & i++) {
len[i] = new int[n];
for (int j = 0; j & j++)
scanf("%d", &len[i][j]); } node a2b = {}, *c = &a2b, *d, *f; int q, a, b, scanf("%d", &q); for (int i = 0; i & i++) {
c-&next = new node{ i,0,0 };
c = c-& } while (q--) {
scanf("%d%d", &a, &b);
if(g[a]==0 && g[b]==0)
a2b.next = 0;
while (c != 0)
c-&len = len[a][e];
insert(c, &a2b);
while (c-&next != 0)
while (d-&next != 0)
l = c-&len + len[c-&name][f-&name];
if (l & f-&len)
len[a][f-&name] =
len[f-&name][a] =
d-&next = f-&
insert(f, c);
if (d-&next == f)
g[a] == 0;
printf("%d\n", len[a][b]); }}
by 28389 三月 13,
Solution_ID:17009& && && && &拿好不谢。
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
http://blog.csdn.net/qq_/article/details/
by 30428 三月 6,
Solution_ID:16911& && && && &by Eden
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
这道题比较麻烦，但我很久以前就AC了。现在我只是求博客题解的访客数量网址：/eden_/blog/static//
by 21413 二月 28,
Solution_ID:16404& && && && &为远方，付出别人无法企及的努力！
& && && && & & && &时间复杂度：Θ（常数有点大) 空间复杂度：Θ（n^2)
#include&cstdio&#include&algorithm&#include&cmath&#include&cstring&#include&cstdlib&struct city{ int x1,x2,x3,x4,y1,y2,y3,y4,t;};struct aa{
int x,y;};city c[109];int n,s,t,a,b,aa v[800];double map[800][800];double ans[800]; bool bb[800];void suan(int &x4,int &y4,int x1,int y1,int x2,int y2,int x3,int y3){ if ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)==(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)+(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3))
x4=(x1+x2)-x3;
y4=(y1+y2)-y3; }
if ((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)==(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3))
x4=(x1+x3)-x2;
y4=(y1+y3)-y2; } if ((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)==(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)+(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
x4=(x3+x2)-x1;
y4=(y3+y2)-y1; }
}int main(){ scanf("%d",&n); for (int kk=1;kk&=n;kk++) {
scanf("%d%d%d%d",&s,&t,&a,&b);
for (int i=1;i&=s;i++)
scanf("%d%d%d%d%d%d%d",&c[i].x1,&c[i].y1,&c[i].x2,&c[i].y2,&c[i].x3,&c[i].y3,&c[i].t);
suan(c[i].x4,c[i].y4,c[i].x1,c[i].y1,c[i].x2,c[i].y2,c[i].x3,c[i].y3);
//printf("%d %d\n",c[i].x4,c[i].y4);
memset(map,0,sizeof(a));
memset(v,0,sizeof(v));
memset(bb,false,sizeof(b));
for(int i=1;i&=s;i++)
v[(i-1)*4+1].x=c[i].x1;
v[(i-1)*4+1].y=c[i].y1;
v[(i-1)*4+2].x=c[i].x2;
v[(i-1)*4+2].y=c[i].y2;
v[(i-1)*4+3].x=c[i].x3;
v[(i-1)*4+3].y=c[i].y3;
v[(i-1)*4+4].x=c[i].x4;
v[(i-1)*4+4].y=c[i].y4;
for (int i=1;i&=i++)ans[i]=;
//for (int i=1;i&=i++)printf("%d %d\n",v[i].x,v[i].y);
for (int i=1;i&=s;i++)
if (i!=a&&i!=b)
for (int j=(i-1)*4+1;j&=i*4;j++)
for (int l=(i-1)*4+1;l&=i*4;l++)
map[j][l]=c[i].t*sqrt((v[j].x-v[l].x)*(v[j].x-v[l].x)+(v[j].y-v[l].y)*(v[j].y-v[l].y));
for (int j=(i-1)*4+1;j&=i*4;j++)
for (int l=1;l&=l++) if ((l-1)/4+1!=i)
map[j][l]=t*sqrt((v[j].x-v[l].x)*(v[j].x-v[l].x)+(v[j].y-v[l].y)*(v[j].y-v[l].y));
} /* for (int i=1;i&=i++)
for (int j=1;j&=j++)printf("%.2f ",map[i][j]);
printf("\n");
ans[(a-1)*4+1]=0;
for (int i=1;i&=i++)
x=0x3f3f3f3f;
for (int j=1;j&=j++)if (ans[j]&x&&!bb[j])
// printf("%d\n",y);
for (int j=1;j&=j++)if (ans[j]&ans[y]+map[y][j]&&!bb[j])
ans[j]=ans[y]+map[y][j];
} // for (int i=1;i&=i++)printf("%d ",ans[i]);
printf("%.1f",ans[b*4]); }
return 0;}这里写题解
by 29159 二月 8,
Solution_ID:15013& && && && &好像比较水=
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
writer： QWsin一开始没想到直接最短路= =
后来发现直接将每个点拆散
同城市的处理公路那条边，不同的处理飞机那条边
水水的邻接矩阵和floyd#include&iostream&#include&algorithm&#include&cstdio&#include&cstring&#include&cmath&const int maxn=100+10;struct Point{
Point(int x,int y,int id):x(x),y(y),id(id){}
Point(){}}p[maxn*4];int car[maxn],fly,start,end,n;double dist1(int x1,int x2)
//判断直角需要平方
为了防止浮点误差
不采用先开根后平方的办法{
int xx=p[x1].x-p[x2].x;
int yy=p[x1].y-p[x2].y;
return xx*xx+yy*}double dist(int x1,int x2){
int xx=p[x1].x-p[x2].x;
int yy=p[x1].y-p[x2].y;
return sqrt(xx*xx+yy*yy);}Point cal(int k1,int k2,int k3,int id)
///处理第四个点{
double d12=dist1(k1,k2),d13=dist1(k1,k3),d23=dist1(k2,k3);
//算出距离平方后枚举
if(d12==d13+d23)
//可以手画一下
就能理解为什么这样算了
（比较难讲）
int dx=p[k3].x-p[k1].x;
int dy=p[k3].y-p[k1].y;
return Point(p[k2].x-dx,p[k2].y-dy,id);
if(d23==d12+d13)
int dx=p[k1].x-p[k2].x;
int dy=p[k1].y-p[k2].y;
return Point(p[k3].x-dx,p[k3].y-dy,id);
int dx=p[k2].x-p[k1].x;
int dy=p[k2].y-p[k1].y;
return Point(p[k3].x-dx,p[k3].y-dy,id);}double G[maxn*4][maxn*4];void init_G(int n){
for(int i=1;i&=4*n;i++)
for(int j=1;j&=4*n;j++)
G[i][j]=(1&&30);}void Floyd(){
for(int k=1;k&=4*n;k++)
for(int i=1;i&=4*n;i++)
for(int j=1;j&=4*n;j++)
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);}int main(){
int T;cin&&T;
while(T--)
scanf("%d%d%d%d",&n,&fly,&start,&end);
for(int i=1;i&=n;i++)
int k1=(i-1)*4+1,k2=k1+1,k3=k1+2,k4=k1+3;
/////一个城市四个点
一号城市为1 2 3 4
二号为5 6 7 8
scanf("%d%d%d%d%d%d%d",&p[k1].x,&p[k1].y,&p[k2].x,&p[k2].y,&p[k3].x,&p[k3].y,&car[i]);
p[k1].id=p[k2].id=p[k3].id=i;
///id是所在城市
p[k4]=cal(k1,k2,k3,i);
init_G(n);
for(int i=1;i&=4*n;i++)
////对于每个点 处理它到另外所有点的边
for(int j=1;j&=4*n;j++)
if(p[i].id==p[j].id)
//在同一个城市
G[i][j]=min(G[i][j],dist(i,j)*car[p[i].id]);
G[i][j]=min(G[i][j],dist(i,j)*fly);
double ans=(1&&30);
for(int i=4*start-3;i&=4*i++)
for(int j=4*end-3;j&=4*j++)
ans=min(ans,G[i][j]);
printf("%.1f\n",ans);
return 0;}
by 19812 十二月 3,
Solution_ID:12943& && && && &SLYZ签到
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
关键看第四点的求法
by 28413 十月 18,
Solution_ID:12198& && && && &floyd算法(带注释)
& && && && & & && &时间复杂度：Θ（o(n^3)) 空间复杂度：Θ（o(n^2))
代码#include&cstdio&
#include&cmath&
#include&iostream&
#define INF 1e20
//有下划线的都是宏
#define FOR(i,x) for(int i=1;i&=(x);i++)
#define For(i,x,y) for(int i=(x);i&=(y);i++)
#define pf(x)
#define far(a,b) sqrt(pf(d[a][0]-d[b][0])+pf(d[a][1]-d[b][1]))
#define MAX(a,b,c) max(a,max(b,c))
#define IF(x,y)
int d[2001][2],p[1001],c[2001];
//d[a][]表示机场a的坐标,
p[x]表示城市x的高速公路价格,
c[a]表示机场a所属的城市
int A,B,t,
//sum表示城市个数,
t为单位路程飞机的价格,
A,B分别为起点,终点
double g[];
void readin(),cal(int),gz(int* ,int* ,int* ,int*),ycl();
double floyd();
int main(){
scanf("%d",&z);
while(z--){
readin();ycl();
printf("%.1lf\n",floyd());
//建议换成四次dijskra,比一次floyd要略快
void readin(){
//数据读入
scanf("%d%d%d%d",&sum,&t,&A,&B);
FOR(i,sum){
//用宏简化代码
scanf("%d%d",&d[(i-1)*4+j][0],&d[(i-1)*4+j][1]);
c[(i-1)*4+j]=i;
//求该城市第4个机场的坐标
scanf("%d",&p[i]);
//此时sum表示机场的个数
void cal(int x){
//求第四个机场的坐标
double k1=far(x-2,x-3),k2=far(x-1,x-3),k3=far(x-2,x-1),maxx=MAX(k1,k2,k3);//maxx是已知三点所构成的直角三角形的斜边长
if(maxx==k1)gz(d[x-1],d[x-3],d[x-2],d[x]); //判断直角顶点
else if(maxx==k2)gz(d[x-2],d[x-1],d[x-3],d[x]);
else if(maxx==k3)gz(d[x-3],d[x-2],d[x-1],d[x]);
void ycl(){
//预处理两点之间的直接距离
FOR(i,sum)FOR(j,sum)
IF(c[i],c[j]) g[i][j]=far(i,j)*p[c[i]]; //同一城市
else g[i][j]=far(i,j)*t;
//不在同一城市
double floyd(){
FOR(k,sum) FOR(i,sum) FOR(j,sum)
//floyd,时间复杂度o(n^3),劣于dijskra(但是floyd非常好写^-^)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
double mina=INF;
For(i,(A-1)*4+1,A*4)
For(j,(B-1)*4+1,B*4)
mina=min(mina,g[i][j]);
//起点有四个,终点有四个,枚举求最短的一条路
void gz(int*a,int*b1,int*b2,int*x){x[0]=b1[0]+b2[0]-a[0],x[1]=b1[1]+b2[1]-a[1];}//计算第四点(第四个机场)的坐标运行结果测试点#10410.in
结果:&label&AC&/label&
内存使用量:
时间使用量:
测试点#10411.in
结果:&label&AC&/label&
内存使用量:
时间使用量:
测试点#10412.in
结果:&label&AC&/label&
内存使用量:
时间使用量:
测试点#10413.in
结果:&label&AC&/label&
内存使用量:
时间使用量:
测试点#10414.in
结果:&label&AC&/label&
内存使用量:
时间使用量:
鄙人的用户名: 奋舟
by 28599 十月 2,