HDU 2066 最短路floyd算法+优化

http://acm.hdu.edu.cn/showproblem.php?pid=206

题意 从任意一个邻居家出发 到达任意一个终点的 最小距离

解析 求多源最短路 我想到的是Floyd算法 但是题目给出的n的大小不确定 所以图很稀疏 会有很多孤立点 会多跑很多没用的路径 需要优化一下 不然会超时

　　我看其他人很多都是用迪杰斯特拉写的，可以试试

AC代码

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <ctime>

 #include <vector>

 using namespace std;

 const int maxn= 1e3+;

 const int maxm= 1e8+;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 int dp[maxn][maxn],a[maxn][maxn];

 int n,m,t,l[maxn],q[maxn];

 int main()

 {

     while(scanf("%d %d %d",&n,&m,&t)!=EOF)

     {

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

             for(int j=;j<=maxn;j++)    //初始化长度

             {

                 if(i==j)

                     dp[i][j]=;

                 else

                     dp[i][j]=inf;

             }

          int x,y,d;

          int maxx=;

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

          {

              scanf("%d %d %d",&x,&y,&d);

              maxx=max(maxx,max(x,y));

              if(dp[x][y]>d)

                 dp[x][y]=dp[y][x]=d;　　　　　　　　//有平行边 更新为最小的边权

          }

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

             scanf("%d",&l[i]);

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

             scanf("%d",&q[i]);

          for(int k=;k<=maxx;k++)　　　　　　　　　　//三个 for Floyd板子

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

                 if(dp[i][k]!=inf)　　　　　　　　　　　//优化一下 如果边为inf直接跳过第三个for

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

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

          int ans=inf;

          for(int i=;i<m;i++)　　　　　　　　　　　　　　//枚举起点和终点组成的路径 找最小值

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

                 ans=min(ans,dp[l[i]][q[j]]);

         printf("%d\n",ans);

     }

     return ;

 }