P2009 跑步

热烈庆祝SZM黄题破80，绿题破30，蓝题破20！！！（紫题还是2，，，，orz%%%）

非常水的一道最短路，小于等于100果断Floyd，要好好读题，别忘记特判，8分钟基本就能做出来啦~~~

参考程序如下：

 #include<iostream>

 #include<cstring>

 #define inf 336860180

 using namespace std;

 int dist[][],n,k,x,y,z;

 char a,b;

 int main()

 {

     memset(dist,,sizeof(dist));

     cin>>n>>k;

     for(int i=;i<=n;i++)

     {

         cin>>z;

         if(i!=n)x=i,y=i+;

         else x=i,y=;

         if(dist[x][y]==inf)dist[x][y]=dist[y][x]=z;

         else dist[x][y]=dist[y][x]=max(dist[x][y],z);

     }

     for(int i=;i<=k;i++)

     {

         cin>>a>>b>>z;

         x=(a-'A'+);y=(b-'A'+);

         if(dist[x][y]==inf)dist[x][y]=dist[y][x]=z;

         else dist[x][y]=dist[y][x]=max(dist[x][y],z);

     }

     for(int k=;k<=n;k++)

     {

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

             }

         }

     }

     cin>>a>>b;

     x=a-'A'+;y=b-'A'+;

     cout<<dist[x][y];

     return ;

 }

巴特西

P2009 跑步

最新文章

热门文章