滞りなく工事を再開する
2624 ワード
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19930 Accepted Submission(s): 6240
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数C(C<=100)であり、小島の個数を表し、次いでCグループの座標であり、各小島の座標を表し、これらの座標は0<=x、y<=1000の整数である.
Output
各入力データのセットは、ブリッジの最小コストを表す行を出力し、結果は小数点以下を保持します.すべてをスムーズにするために工事が実現できない場合は、「oh!」を出力します.
Sample Input
Sample Output
本題の大意は条件を満たす場合、もっと費用がかかり、提出時にコンパイルエラーに遭遇し、分析の結果、この場所が間違っていたことが分かった.w=sqrt(1.0*pow(a[i]-a[j],2)+pow(b[i]-b[j],2));w=sqrt(pow(1.0*a[i]-a[j],2)+pow(1.0*b[i]-b[j],2))と書くべきである.なぜならdouble pow(double a,double b)
関数名:pow功 機能: 指数関数(xのy次方)用 法: double pow(double x, double y); したがって、結果は正しいが、コミット時にコンパイルエラーが発生した.
Total Submission(s): 19930 Accepted Submission(s): 6240
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数C(C<=100)であり、小島の個数を表し、次いでCグループの座標であり、各小島の座標を表し、これらの座標は0<=x、y<=1000の整数である.
Output
各入力データのセットは、ブリッジの最小コストを表す行を出力し、結果は小数点以下を保持します.すべてをスムーズにするために工事が実現できない場合は、「oh!」を出力します.
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2
oh!
本題の大意は条件を満たす場合、もっと費用がかかり、提出時にコンパイルエラーに遭遇し、分析の結果、この場所が間違っていたことが分かった.w=sqrt(1.0*pow(a[i]-a[j],2)+pow(b[i]-b[j],2));w=sqrt(pow(1.0*a[i]-a[j],2)+pow(1.0*b[i]-b[j],2))と書くべきである.なぜならdouble pow(double a,double b)
関数名:pow功 機能: 指数関数(xのy次方)用 法: double pow(double x, double y); したがって、結果は正しいが、コミット時にコンパイルエラーが発生した.
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 1000000
double eg[400][400],vid[1000];
int a[1000],b[1000],p[1000];
int n,m;
void prim()
{
int k,r;
double min;
memset(p,0,sizeof(p));
for(int i=1;i<=m;i++)
vid[i]=eg[1][i];
p[1]=1;
vid[1]=0;
for(int i=2;i<=m;i++)
{
min=M;
k=1;
for(int j=1;j<=m;j++)
if(!p[j]&&vid[j]<min)
{
min=vid[j];
k=j;
}
if(min==M)
{
printf("oh!
"); //break;
return ;
}
p[k]=1;
for(int t=1;t<=m;t++)
if(!p[t]&&vid[t]>eg[k][t])
vid[t]=eg[k][t];
}
double sum=0;
for(int i=2;i<=m;i++)
sum+=vid[i]*100;
printf("%.1lf
",sum);
return ;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int i,j,k;
scanf("%d",&m);
for(i=1;i<=m;i++)
scanf("%d%d",&a[i],&b[i]);
double w;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
{
w=sqrt(pow(1.0*a[i]-a[j],2)+pow(1.0*b[i]-b[j],2));
if(w>=10&&w<=1000)
eg[i][j]=w;
else eg[i][j]=M;
}
memset(vid,0,sizeof(vid));
prim();
}
return 0;
}