2050 Programming Competition (CCPC)

Pro&Sol

链接: https://pan.baidu.com/s/17Tt3EPKEQivP2-3OHkYD2A 提取码: wbnu 复制这段内容后打开百度网盘手机App，操作更方便哦

6491时间间隔

 #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+;
 const int inf=1e9;
 const double eps=1e-;

 char s[maxn],str[]="";

 int main()
 {
     int t,len,i;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%s",s);
         len=strlen(s);
         for (i=;i<len;i++)
             if (s[i]!=str[i%])
                 break;
         if (i==len && len%==)
             printf("Yes\n");
         else
             printf("No\n");
     }
     return ;
 }
 /*

 */

6491时间间隔

S距离2050年1月1日0点0时0分多少秒

2050_value-this_value 而不是差值绝对值模100 (不过感觉有点牵强)

负数的结果进行相应处理

 #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+;
 const int inf=1e9;
 const double eps=1e-;

 int main()
 {
     int t,a,b,c,d,e,f;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%d-%d-%d %d:%d:%d",&a,&b,&c,&d,&e,&f);
         printf("%d\n",((-e*-f)%+)%);
     }
     return ;
 }
 /*
 7
 2023-12-01 03:12:12
 68
 2024-05-01 03:12:12
 68
 3000-03-01 23:00:59
 41
 6000-03-01 00:00:00
 0
 6661-01-12 13:34:45
 15
 6661-01-12 13:34:46
 14
 2049-12-31 23:59:59
 1
 */

 #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+;
 const int inf=1e9;
 const double eps=1e-;

 int mon[]={,,,,,,,,,,,,};

 ll cal(int a,int b,int c,int d,int e,int f)
 {
     ll sum=;
     int i;
     for (i=;i<a;i++)
         if (i%== && (i%== || i%!=))
             sum+=1ll****;
         else
             sum+=1ll****;
     if (i%== && (i%== || i%!=))
         mon[]=;
     for (i=;i<b;i++)
         sum+=1ll****mon[i];
     sum+=1ll****(c-)+d**+e*+f;
     return sum;
 }

 int main()
 {
     int t,a,b,c,d,e,f;
     ll tot=;
     tot=cal(,,,,,);
     scanf("%d",&t);
     while (t--)
     {
         scanf("%d-%d-%d %d:%d:%d",&a,&b,&c,&d,&e,&f);
         printf("%lld\n",(tot-cal(a,b,c,d,e,f)%+)%);
     }
     return ;
 }
 /*

 */

 import java.text.SimpleDateFormat;
 import java.util.*;

 public class Main {
     public static void main(String[] args) throws Exception {
         //upper lower
         SimpleDateFormat tf=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
         Date t1=tf.parse("2050-01-01 00:00:00");
         Scanner in=new Scanner(System.in);
         String s;
         int t;
         t=in.nextInt();
         s=in.nextLine();
         while (t-->0) {
             s=in.nextLine();
             Date t2=tf.parse(s);
             //System.out.println(t2);    //test
             //System.out.println(t2.getTime()/1000);
             //ms
             System.out.println(( Math.abs(t1.getTime()-t2.getTime()) )/1000%100);
 //            System.out.println(dif);
         }
         in.close();
     }
 }
 /*
 7
 2023-12-01 03:12:12
 2024-05-01 03:12:12
 2000-03-01 23:00:59
 2049-03-01 00:00:00
 2048-01-12 13:34:45
 2023-01-12 13:34:46
 2036-12-31 23:59:59

 68
 68
 41
 0
 15
 14
 1
 */

6492分宿舍

贪心，参见下方注释

 #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+;
 const int inf=1e9;
 const double eps=1e-;

 ll n,m,k,a,b,c;

 ll cal(ll g)
 {
     /*
     替代 2*3=3*2
     两人间 <=2
     三人间 <=1
     */
     ll tot=1e18;
     int i;
     for (i=;i<=;i++)
         tot=min(tot,i*a+(g-i*+)/*b);
     for (i=;i<=;i++)
         tot=min(tot,(g-i*+)/*a+i*b);
     return tot;
 }

 int main()
 {
     ll tot;
     int t,i;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c);
         tot=1e18;
         for (i=k;i>=;i--)
             tot=min(tot,c*i+cal(n+k-i)+cal(m+k-i));

         printf("%lld\n",tot);
     }
     return ;
 }
 /*
 1
 1000 1000 1000 1000000000 1000000000 1000000000

 1
 1 1 0 3 2 1
 */

预处理f[x]，x个人，需要花费的最小代码。对于每个k对应的n+k和m+k，O(1)得到答案。

\( f[i]=min(f[i-2]+a,f[i-3]+b) \\ f[j]=0 j<=0 \)

 #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=2e3+;
 const int inf=1e9;
 const double eps=1e-;

 ll n,m,k,a,b,c,f[maxn];

 int main()
 {
     ll tot;
     int t,i,lim;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c);
         memset(f,sizeof(0x3f),sizeof(f));
         lim=max(n+k,m+k);
         f[]=;
         for (i=;i<=lim;i++)
             if (i<)
                 f[i]=min(f[i],a);
             else
                 f[i]=min(f[i],f[i-]+a);
         for (i=;i<=lim;i++)
             if (i<)
                 f[i]=min(f[i],b);
             else
                 f[i]=min(f[i],f[i-]+b);

         tot=1e18;
         for (i=k;i>=;i--)
             tot=min(tot,c*i+f[n+k-i]+f[m+k-i]);
         printf("%lld\n",tot);
     }
     return ;
 }
 /*
 1
 1000 1000 1000 1000000000 1000000000 1000000000

 1
 1 1 0 3 2 1
 */

暴力，不会超时

#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
*/

以下方法是错误的

6493PASS

 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冰水挑战

无贪心方法等。应该往dp想。c不应该作为一维。应该很自然就能想到。。。

\( 前i个挑战中，选择j个挑战，剩余的最大体力\\ \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*} \)

 #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=1e3+;
 const ll inf=1e18;
 const double eps=1e-;

 ll f[maxn][maxn];

 int main()
 {
     int t,n,i,j;
     ll m,a,b,c;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%d%lld",&n,&m);
         for (i=;i<=n;i++)
             for (j=;j<=n;j++)
                 f[i][j]=-inf;
         f[][]=m;
         for (i=;i<=n;i++)
         {
             scanf("%lld%lld%lld",&a,&b,&c);
             f[i][]=f[i-][]+c;
             for (j=;j<=n;j++)
             {
                 f[i][j]=f[i-][j]+c;
                 if (min(f[i-][j-],b)-a>)
                     f[i][j]=max(f[i][j],min(f[i-][j-],b)-a+c);
             }
         }
         for (j=n;j>=;j--)
             if (f[n][j]>)
                 break;
         printf("%d\n",j);
     }
     return ;
 }
 /*

 */

6496大厦

1.新方法

用下面的方法求矩形

对于每个横坐标小块i，求纵坐标上下限[ d[i] , u[i] ]。

若对于某个纵坐标，横坐标小块为[x1,x2]，则往上，[x3,x4]，有x1<=x3 , x4<=x2。往下，同理。(里大，外小)

对于横坐标小块[x1,x2]，求[x1,x2]的纵坐标上下限([ max(d[x1],d[x1+1],...,d[x2]) , min(u[x1],u[x1+1],...,u[x2])  ])

st/线段树处理。

O(T*(n*m+n*n/2))

横坐标小块12；13；14；..；23；24；...；n-1 n

1*n 个数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)

 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <string>
 #include <algorithm>
 #include <set>
 #include <map>
 #include <queue>
 #include <iostream>
 #include <bitset>
 using namespace std;

 #define ll long long

 const int maxn=1e3+;
 const int maxm=1e3+;
 const int inf=1e9;
 const double eps=1e-;
 const ll mod=1e9+;

 int c1[maxn],c2[maxn];
 bitset<maxm> f[maxn];

 int main()
 {
     ll sum;
     int t,w,h,n,m,i,j,g;
     scanf("%d",&t);
     while (t--)
     {
         scanf("%d%d%d%d",&w,&h,&n,&m);
         for (i=;i<=n;i++)
             scanf("%d",&c1[i]);
         for (i=;i<=m;i++)
             scanf("%d",&c2[i]);

         for (i=;i<=n;i++)
             f[i].reset();

         sort(c1+,c1+n+);
         sort(c2+,c2+m+);
         for (i=;i<=n;i++)
             for (j=;j<=m;j++)
                 if (<=c1[i]+c2[j] && c1[i]+c2[j]<=w*
                     && <=c1[i]-c2[j] && c1[i]-c2[j]<=h*)  ///w*2 h*2 int range
                         f[i].set(j,);

         sum=;
         for (i=;i<n;i++)
             for (j=i+;j<=n;j++)
                 {
                     g=(f[i]&f[j]).count();
                     sum=(sum+1ll*g*(g-)/)%mod;
                 }
         printf("%lld\n",sum); ///ll
     }
     return ;
 }
 /*

 */

6497骑行

 #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=1e3+;
 const int inf=1e9;
 const double eps=1e-;

 double v,t;
 double w[maxn],s[maxn],a[maxn],lim[maxn];

 void work(double v1,double v2,double v0,double len,double a)
 {
     double dist=(v0*v0-v1*v1)//a + (v0*v0-v2*v2)//a;
     double dist1=(v2*v2-v1*v1)//a;
     if (dist<=len)
     {
         t+=(v0-v1)/a + (v0-v2)/a + (len-dist)/v0;
         v=v2;
     }
     else if (v2>v1 && dist1>len)
     {
         v=sqrt(*a*len + v1*v1);
         t+=(v-v1)/a;
     }
     else
     {
         double v3=sqrt((*a*len + v1*v1 + v2*v2)/);
         t+=(v3-v1)/a + (v3-v2)/a;
         v=v2;
     }
 }

 int main()
 {
     double temp;
     int T,n,i;
     scanf("%d",&T);
     while (T--)
     {
         scanf("%d",&n);
         for (i=;i<=n;i++)
             scanf("%lf%lf%lf",&w[i],&s[i],&a[i]);
         lim[n]=s[n];
         for (i=n-;i>=;i--)
         {
             temp=sqrt(*a[i+]*w[i+]+lim[i+]*lim[i+]);
             lim[i]=min(min(s[i],s[i+]),temp);
         }

         v=,t=;
         for (i=;i<=n;i++)
             work(v,lim[i],s[i],w[i],a[i]);
         printf("%.10f\n",t);
     }
     return ;
 }
 /*
 */

6498跨洋飞行

一个点x到另外一个点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，至少dist（x，y）+min y to others（z）。而miny to others是有用的，x到y，剩余z，而y到其它点，至少要使用z，不浪费。除了最后一个点，浪费min n to others。但倒数第二个点到点n，而倒数第二个点到其它点的最短距离有可能不是该点到点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 */