2050 Programming Competition (CCPC)
生活随笔
收集整理的這篇文章主要介紹了
2050 Programming Competition (CCPC)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
?
Pro&Sol
鏈接: https://pan.baidu.com/s/17Tt3EPKEQivP2-3OHkYD2A 提取碼: wbnu 復(fù)制這段內(nèi)容后打開百度網(wǎng)盤手機App，操作更方便哦
?
6491?時間間隔
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e5+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 char s[maxn],str[5]="2050"; 20 21 int main() 22 { 23 int t,len,i; 24 scanf("%d",&t); 25 while (t--) 26 { 27 scanf("%s",s); 28 len=strlen(s); 29 for (i=0;i<len;i++) 30 if (s[i]!=str[i%4]) 31 break; 32 if (i==len && len%4==0) 33 printf("Yes\n"); 34 else 35 printf("No\n"); 36 } 37 return 0; 38 } 39 /* 40 41 */?
6491?時間間隔
S距離2050年1月1日0點0時0分多少秒
2050_value-this_value 而不是差值絕對值模100 (不過感覺有點牽強)
負(fù)數(shù)的結(jié)果進(jìn)行相應(yīng)處理
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e4+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 20 21 int main() 22 { 23 int t,a,b,c,d,e,f; 24 scanf("%d",&t); 25 while (t--) 26 { 27 scanf("%d-%d-%d %d:%d:%d",&a,&b,&c,&d,&e,&f); 28 printf("%d\n",((-e*60-f)%100+100)%100); 29 } 30 return 0; 31 } 32 /* 33 7 34 2023-12-01 03:12:12 35 68 36 2024-05-01 03:12:12 37 68 38 3000-03-01 23:00:59 39 41 40 6000-03-01 00:00:00 41 0 42 6661-01-12 13:34:45 43 15 44 6661-01-12 13:34:46 45 14 46 2049-12-31 23:59:59 47 1 48 */?
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e4+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 20 21 ll cal(int a,int b,int c,int d,int e,int f) 22 { 23 ll sum=0; 24 int i; 25 for (i=1;i<a;i++) 26 if (i%4==0 && (i%400==0 || i%100!=0)) 27 sum+=1ll*366*24*60*60; 28 else 29 sum+=1ll*365*24*60*60; 30 if (i%4==0 && (i%400==0 || i%100!=0)) 31 mon[2]=29; 32 for (i=1;i<b;i++) 33 sum+=1ll*24*60*60*mon[i]; 34 sum+=1ll*24*60*60*(c-1)+d*60*60+e*60+f; 35 return sum; 36 } 37 38 int main() 39 { 40 int t,a,b,c,d,e,f; 41 ll tot=0; 42 tot=cal(2050,1,1,0,0,0); 43 scanf("%d",&t); 44 while (t--) 45 { 46 scanf("%d-%d-%d %d:%d:%d",&a,&b,&c,&d,&e,&f); 47 printf("%lld\n",(tot-cal(a,b,c,d,e,f)%100+100)%100); 48 } 49 return 0; 50 } 51 /* 52 53 */?
1 import java.text.SimpleDateFormat; 2 import java.util.*; 3 4 public class Main { 5 public static void main(String[] args) throws Exception { 6 //upper lower 7 SimpleDateFormat tf=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); 8 Date t1=tf.parse("2050-01-01 00:00:00"); 9 Scanner in=new Scanner(System.in); 10 String s; 11 int t; 12 t=in.nextInt(); 13 s=in.nextLine(); 14 while (t-->0) { 15 s=in.nextLine(); 16 Date t2=tf.parse(s); 17 //System.out.println(t2); //test 18 //System.out.println(t2.getTime()/1000); 19 //ms 20 System.out.println(( Math.abs(t1.getTime()-t2.getTime()) )/1000%100); 21 // System.out.println(dif); 22 } 23 in.close(); 24 } 25 } 26 /* 27 7 28 2023-12-01 03:12:12 29 2024-05-01 03:12:12 30 2000-03-01 23:00:59 31 2049-03-01 00:00:00 32 2048-01-12 13:34:45 33 2023-01-12 13:34:46 34 2036-12-31 23:59:59 35 36 68 37 68 38 41 39 0 40 15 41 14 42 1 43 */?
6492?分宿舍
貪心，參見下方注釋
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e5+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 ll n,m,k,a,b,c; 20 21 ll cal(ll g) 22 { 23 /* 24 替代 2*3=3*2 25 兩人間 <=2 26 三人間 <=1 27 */ 28 ll tot=1e18; 29 int i; 30 for (i=0;i<=2;i++) 31 tot=min(tot,i*a+(g-i*2+2)/3*b); 32 for (i=0;i<=1;i++) 33 tot=min(tot,(g-i*3+1)/2*a+i*b); 34 return tot; 35 } 36 37 int main() 38 { 39 ll tot; 40 int t,i; 41 scanf("%d",&t); 42 while (t--) 43 { 44 scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c); 45 tot=1e18; 46 for (i=k;i>=0;i--) 47 tot=min(tot,c*i+cal(n+k-i)+cal(m+k-i)); 48 49 printf("%lld\n",tot); 50 } 51 return 0; 52 } 53 /* 54 1 55 1000 1000 1000 1000000000 1000000000 1000000000 56 57 1 58 1 1 0 3 2 1 59 */?
預(yù)處理f[x]，x個人，需要花費的最小代碼。對于每個k對應(yīng)的n+k和m+k，O(1)得到答案。
\( f[i]=min(f[i-2]+a,f[i-3]+b) \\ f[j]=0 j<=0 \)
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=2e3+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 ll n,m,k,a,b,c,f[maxn]; 20 21 int main() 22 { 23 ll tot; 24 int t,i,lim; 25 scanf("%d",&t); 26 while (t--) 27 { 28 scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c); 29 memset(f,sizeof(0x3f),sizeof(f)); 30 lim=max(n+k,m+k); 31 f[0]=0; 32 for (i=0;i<=lim;i++) 33 if (i<2) 34 f[i]=min(f[i],a); 35 else 36 f[i]=min(f[i],f[i-2]+a); 37 for (i=0;i<=lim;i++) 38 if (i<3) 39 f[i]=min(f[i],b); 40 else 41 f[i]=min(f[i],f[i-3]+b); 42 43 tot=1e18; 44 for (i=k;i>=0;i--) 45 tot=min(tot,c*i+f[n+k-i]+f[m+k-i]); 46 printf("%lld\n",tot); 47 } 48 return 0; 49 } 50 /* 51 1 52 1000 1000 1000 1000000000 1000000000 1000000000 53 54 1 55 1 1 0 3 2 1 56 */?
暴力，不會超時
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <set> #include <map> #include <queue> #include <iostream> using namespace std; #define ll long long const int maxn=1e5+10; const int inf=1e9; const double eps=1e-8; int main() { int t; ll n,m,k,a,b,c,i,j,tot,sum,x,y; scanf("%d",&t); while (t--) { scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c); tot=1e18; for (i=k;i>=0;i--) { sum=c*i; x=n+k-i; y=1e18; for (j=0;j<=(x+1)/2;j++) y=min(y,j*a+(x-j*2+2)/3*b); sum+=y; x=m+k-i; y=1e18; for (j=0;j<=(x+1)/2;j++) y=min(y,j*a+(x-j*2+2)/3*b); sum+=y; tot=min(tot,sum); } printf("%lld\n",tot); } return 0; } /* 1 1000 1000 1000 1000000000 1000000000 1000000000 1 1 1 0 3 2 1 */?
以下方法是錯誤的
?
6493?PASS
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e4+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 int g[maxn],a[maxn]; 20 21 int main() 22 { 23 int t,n,m,k,i,tot; 24 scanf("%d",&t); 25 while (t--) 26 { 27 scanf("%d%d%d",&n,&m,&k); 28 memset(g,0,sizeof(g)); 29 for (i=1;i<=n;i++) 30 { 31 scanf("%d",&a[i]); 32 g[a[i]]++; 33 } 34 for (i=1;i<=m;i++) 35 g[i]/=k; 36 tot=0; 37 for (i=1;i<=n/2;i++) 38 { 39 g[a[i]]--; 40 if (g[a[i]]>=0) 41 tot++; 42 } 43 printf("%d\n",tot); 44 } 45 return 0; 46 } 47 /* 48 49 */?
1005球賽
一開始猜測貪心有可能是錯的，所以選擇使用dp
\( \begin{equation*}\begin{split}&condition \quad (a,b) \quad -> \quad condition (x,y) \quad + \quad c(+1/+0)\\&(10,k)/(k,10) \quad -> \quad (0,0) \quad [(11,k)/(k,11)] \quad + \quad 1 \quad k<=9\\&(10,11)/(11,10) \quad -> \quad (0,0) \quad [(10,12)/(12,10)] \quad +1\\&(10,11)/(11,10) \quad -> \quad (10,10) \quad [(11,11)]\\&f[x][y]=max(f[a][b]+c)\end{split}\end{equation*} \)
?
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <set> #include <map> #include <queue> #include <iostream> using namespace std; #define ll long long const int maxn=1e4+10; const int inf=1e9; const double eps=1e-8; char str[maxn]; int f[maxn][12][12]; int main() { int T,g,len,i,j,k,s,t; scanf("%d",&T); while (T--) { scanf("%s",str+1); len=strlen(str+1); for (i=0;i<=len;i++) for (j=0;j<12;j++) for (k=0;k<12;k++) f[i][j][k]=-1; f[0][0][0]=0; for (i=1;i<=len;i++) { for (j=0;j<12;j++) for (k=0;k<12;k++) if (f[i-1][j][k]!=-1) { if (str[i]=='A' || str[i]=='?') { s=j+1; t=k; if (s==11 && t==11) s=10,t=10; if ((s>=11 && s-t>=2) || (t>=11 && t-s>=2)) f[i][0][0]=max(f[i][0][0],f[i-1][j][k]+1); else f[i][s][t]=max(f[i][s][t],f[i-1][j][k]); } if (str[i]=='B' || str[i]=='?') { s=j; t=k+1; if (s==11 && t==11) s=10,t=10; if ((s>=11 && s-t>=2) || (t>=11 && t-s>=2)) f[i][0][0]=max(f[i][0][0],f[i-1][j][k]+1); else f[i][s][t]=max(f[i][s][t],f[i-1][j][k]); } } } g=0; for (i=0;i<12;i++) for (j=0;j<12;j++) g=max(g,f[len][i][j]); printf("%d\n",g); } return 0; } /* 1 AAAAAAAAAAA ?????????????????????? ????? */?
6495?冰水挑戰(zhàn)
無貪心方法等。應(yīng)該往dp想。c不應(yīng)該作為一維。應(yīng)該很自然就能想到。。。
\( 前i個挑戰(zhàn)中，選擇j個挑戰(zhàn)，剩余的最大體力\\ \begin{equation*}\begin{split}&f[i][j]=f[i-1][j]+c_{i}\\&f[i][j]=max(f[i][j],min(f[i-1][j-1],b_{i})-a_{i}+c_{i})) \quad if \, min(f[i-1][j-1],b_{i})-a_{i}>0 \, , \, i>0 \\\end{split}\end{equation*} \)
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e3+10; 16 const ll inf=1e18; 17 const double eps=1e-8; 18 19 ll f[maxn][maxn]; 20 21 int main() 22 { 23 int t,n,i,j; 24 ll m,a,b,c; 25 scanf("%d",&t); 26 while (t--) 27 { 28 scanf("%d%lld",&n,&m); 29 for (i=0;i<=n;i++) 30 for (j=1;j<=n;j++) 31 f[i][j]=-inf; 32 f[0][0]=m; 33 for (i=1;i<=n;i++) 34 { 35 scanf("%lld%lld%lld",&a,&b,&c); 36 f[i][0]=f[i-1][0]+c; 37 for (j=1;j<=n;j++) 38 { 39 f[i][j]=f[i-1][j]+c; 40 if (min(f[i-1][j-1],b)-a>0) 41 f[i][j]=max(f[i][j],min(f[i-1][j-1],b)-a+c); 42 } 43 } 44 for (j=n;j>=1;j--) 45 if (f[n][j]>0) 46 break; 47 printf("%d\n",j); 48 } 49 return 0; 50 } 51 /* 52 53 */?
6496?大廈
1.新方法
用下面的方法求矩形
對于每個橫坐標(biāo)小塊i，求縱坐標(biāo)上下限[ d[i] , u[i] ]。
若對于某個縱坐標(biāo)，橫坐標(biāo)小塊為[x1,x2]，則往上，[x3,x4]，有x1<=x3 , x4<=x2。往下，同理。(里大，外小)
對于橫坐標(biāo)小塊[x1,x2]，求[x1,x2]的縱坐標(biāo)上下限([ max(d[x1],d[x1+1],...,d[x2]) , min(u[x1],u[x1+1],...,u[x2])? ])
st/線段樹處理。
O(T*(n*m+n*n/2))
橫坐標(biāo)小塊12；13；14；..；23；24；...；n-1 n
1*n 個數(shù)n+(n-1)+(n-2)+...+1 = n*(n+1)/2
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e3+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 const ll mod=1e9+7; 19 20 int c1[maxn],c2[maxn],d[maxn],u[maxn]; 21 22 int main() 23 { 24 ll sum; 25 int t,w,h,n,m,i,j,down,up; 26 scanf("%d",&t); 27 while (t--) 28 { 29 scanf("%d%d%d%d",&w,&h,&n,&m); 30 for (i=1;i<=n;i++) 31 scanf("%d",&c1[i]); 32 for (i=1;i<=m;i++) 33 scanf("%d",&c2[i]); 34 memset(d,0x3f,sizeof(d)); 35 memset(u,0,sizeof(u)); 36 37 sort(c1+1,c1+n+1); 38 sort(c2+1,c2+m+1); 39 for (i=1;i<=n;i++) 40 ///其實用二分更快 41 for (j=1;j<=m;j++) 42 if (0<=c1[i]+c2[j] && c1[i]+c2[j]<=w*2 43 && 0<=c1[i]-c2[j] && c1[i]-c2[j]<=h*2) ///w*2 h*2 int range 44 d[i]=min(d[i],j),u[i]=max(u[i],j); 45 46 sum=0; 47 for (i=1;i<n;i++) 48 { 49 down=d[i],up=u[i]; 50 for (j=i+1;j<=n;j++) 51 { 52 down=max(down,d[j]),up=min(up,u[j]); 53 if (up>=down) 54 sum=(sum+1ll*(up-down)*(up-down+1)/2)%mod; 55 } 56 } 57 printf("%lld\n",sum); ///ll 58 } 59 return 0; 60 } 61 /* 62 63 */?
2.bitset(題解)
time(/32)
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 #include <bitset> 12 using namespace std; 13 14 #define ll long long 15 16 const int maxn=1e3+10; 17 const int maxm=1e3+10; 18 const int inf=1e9; 19 const double eps=1e-8; 20 const ll mod=1e9+7; 21 22 int c1[maxn],c2[maxn]; 23 bitset<maxm> f[maxn]; 24 25 int main() 26 { 27 ll sum; 28 int t,w,h,n,m,i,j,g; 29 scanf("%d",&t); 30 while (t--) 31 { 32 scanf("%d%d%d%d",&w,&h,&n,&m); 33 for (i=1;i<=n;i++) 34 scanf("%d",&c1[i]); 35 for (i=1;i<=m;i++) 36 scanf("%d",&c2[i]); 37 38 for (i=1;i<=n;i++) 39 f[i].reset(); 40 41 sort(c1+1,c1+n+1); 42 sort(c2+1,c2+m+1); 43 for (i=1;i<=n;i++) 44 for (j=1;j<=m;j++) 45 if (0<=c1[i]+c2[j] && c1[i]+c2[j]<=w*2 46 && 0<=c1[i]-c2[j] && c1[i]-c2[j]<=h*2) ///w*2 h*2 int range 47 f[i].set(j,1); 48 49 sum=0; 50 for (i=1;i<n;i++) 51 for (j=i+1;j<=n;j++) 52 { 53 g=(f[i]&f[j]).count(); 54 sum=(sum+1ll*g*(g-1)/2)%mod; 55 } 56 printf("%lld\n",sum); ///ll 57 } 58 return 0; 59 } 60 /* 61 62 */?
6497?騎行
?
?
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e3+10; 16 const int inf=1e9; 17 const double eps=1e-8; 18 19 double v,t; 20 double w[maxn],s[maxn],a[maxn],lim[maxn]; 21 22 void work(double v1,double v2,double v0,double len,double a) 23 { 24 double dist=(v0*v0-v1*v1)/2/a + (v0*v0-v2*v2)/2/a; 25 double dist1=(v2*v2-v1*v1)/2/a; 26 if (dist<=len) 27 { 28 t+=(v0-v1)/a + (v0-v2)/a + (len-dist)/v0; 29 v=v2; 30 } 31 else if (v2>v1 && dist1>len) 32 { 33 v=sqrt(2*a*len + v1*v1); 34 t+=(v-v1)/a; 35 } 36 else 37 { 38 double v3=sqrt((2*a*len + v1*v1 + v2*v2)/2); 39 t+=(v3-v1)/a + (v3-v2)/a; 40 v=v2; 41 } 42 } 43 44 int main() 45 { 46 double temp; 47 int T,n,i; 48 scanf("%d",&T); 49 while (T--) 50 { 51 scanf("%d",&n); 52 for (i=1;i<=n;i++) 53 scanf("%lf%lf%lf",&w[i],&s[i],&a[i]); 54 lim[n]=s[n]; 55 for (i=n-1;i>=1;i--) 56 { 57 temp=sqrt(2*a[i+1]*w[i+1]+lim[i+1]*lim[i+1]); 58 lim[i]=min(min(s[i],s[i+1]),temp); 59 } 60 61 v=0,t=0; 62 for (i=1;i<=n;i++) 63 work(v,lim[i],s[i],w[i],a[i]); 64 printf("%.10f\n",t); 65 } 66 return 0; 67 } 68 /* 69 */?
6498?跨洋飛行
一個點x到另外一個點y，到達(dá)點y時，要預(yù)留min(y to others)的油。參見題解。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e3+10; 16 const int inf=1e9; 17 const double eps=1e-10; 18 19 double x[maxn],y[maxn],dist[maxn],road[maxn][maxn],mr[maxn]; 20 bool vis[maxn]; 21 22 int main() 23 { 24 double a,b,c,d,u; 25 int t,n,i,j,p; 26 scanf("%d",&t); 27 while (t--) 28 { 29 scanf("%d%lf%lf%lf%lf%lf",&n,&a,&b,&c,&d,&u); 30 a+=b; 31 for (i=1;i<=n;i++) 32 scanf("%lf%lf",&x[i],&y[i]); 33 for (i=1;i<=n;i++) 34 mr[i]=1.0e18; 35 for (i=1;i<n;i++) 36 for (j=i+1;j<=n;j++) 37 { 38 road[i][j]=road[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ); 39 mr[i]=min(mr[i],road[i][j]); 40 mr[j]=min(mr[j],road[i][j]); 41 } 42 mr[1]=0; /// 43 for (i=0;i<=n;i++) 44 dist[i]=1.0e18; 45 dist[1]=0; 46 memset(vis,0,sizeof(vis)); 47 for (i=1;i<n;i++) 48 { 49 p=0; 50 for (j=1;j<=n;j++) 51 if (!vis[j] && dist[p]>dist[j]) 52 p=j; 53 if (p==n) 54 break; 55 vis[p]=1; 56 for (j=1;j<=n;j++) 57 if (!vis[j] && mr[j]+road[p][j]<u+eps && dist[j]>dist[p] +a + road[p][j]*d + (mr[j]+road[p][j]-mr[p])*c) 58 dist[j]=dist[p] +a + road[p][j]*d + (mr[j]+road[p][j]-mr[p])*c; 59 } 60 printf("%.10f\n",dist[n]); 61 } 62 return 0; 63 } 64 /* 65 66 */?
錯誤想法：
下界提高，x到y(tǒng)，至少dist（x，y）+min y to others（z）。而miny to others是有用的，x到y(tǒng)，剩余z，而y到其它點，至少要使用z，不浪費。除了最后一個點，浪費min n to others。但倒數(shù)第二個點到點n，而倒數(shù)第二個點到其它點的最短距離有可能不是該點到點n的距離。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <iostream> 11 using namespace std; 12 13 #define ll long long 14 15 const int maxn=1e3+10; 16 const int inf=1e9; 17 const double eps=1e-10; 18 19 double x[maxn],y[maxn],dist[maxn],road[maxn][maxn],mr[maxn]; 20 bool vis[maxn]; 21 22 int main() 23 { 24 double a,b,c,d,u; 25 int t,n,i,j,p; 26 scanf("%d",&t); 27 while (t--) 28 { 29 scanf("%d%lf%lf%lf%lf%lf",&n,&a,&b,&c,&d,&u); 30 a+=b; 31 for (i=1;i<=n;i++) 32 scanf("%lf%lf",&x[i],&y[i]); 33 for (i=1;i<=n;i++) 34 mr[i]=1.0e18; 35 for (i=1;i<n;i++) 36 for (j=i+1;j<=n;j++) 37 { 38 road[i][j]=road[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ); 39 mr[i]=min(mr[i],road[i][j]); 40 mr[j]=min(mr[j],road[i][j]); 41 } 42 for (i=1;i<=n;i++) 43 for (j=1;j<=n;j++) 44 if (i!=j && road[i][j]+mr[i]>u+eps) 45 road[i][j]=-1; 46 else 47 road[i][j]=road[i][j]*(c+d)+a; 48 for (i=0;i<=n;i++) 49 dist[i]=1.0e18; 50 dist[1]=0; 51 memset(vis,0,sizeof(vis)); 52 for (i=1;i<n;i++) 53 { 54 p=0; 55 for (j=1;j<=n;j++) 56 if (!vis[j] && dist[p]>dist[j]) 57 p=j; 58 if (p==n) 59 break; 60 vis[p]=1; 61 for (j=1;j<=n;j++) 62 if (!vis[j] && road[p][j]!=-1 && dist[j]>dist[p]+road[p][j]) 63 dist[j]=dist[p]+road[p][j]; 64 } 65 printf("%.10f\n",dist[n]+mr[n]*c); 66 } 67 return 0; 68 } 69 /* 70 71 */?
轉(zhuǎn)載于:https://www.cnblogs.com/cmyg/p/10713800.html
總結(jié)
以上是生活随笔為你收集整理的2050 Programming Competition (CCPC)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： TCP/IP原理 (一)
- 下一篇： 项目需求分析与建议-NABCD模型