程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HLJOJ1015(變形的多源最短路徑)

HLJOJ1015(變形的多源最短路徑)

編輯:C++入門知識

HLJOJ1015(變形的多源最短路徑)


題意:n,m,k,有n個村莊,有k條路,每個村莊有個電話亭,現在要在這些村莊中設一個中心電話亭,每個村莊的快遞員需要帶中心村莊報道然後返回(有向圖),有m台電話,如果村莊配置電話的話就不需要去報道,求快遞員最少總共走了多少路

 

思路:先用floyd預處理下,然後求到每個村莊的最短路總和,比較最小的,這個就是中心電話亭,然後將這些和由大到小排序,減去前m大的

 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const int maxn = 200;
const int INF = 10000000;
int dis[maxn][maxn];
int n, m , k;
 
void floyd()
{
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j],dis[i][k]+ dis[k][j]);
 
}
 
int main()
{
#ifdef xxz
    freopen("in.txt","r",stdin);
#endif // xxz
    int Case = 1;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i = 0; i < n ; i++)
            for(int j = 0; j < n; j++)
                i == j ? dis[i][j] = 0 : dis[i][j] = INF;
 
        for(int i = 0; i < k; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            dis[a- 1][b - 1] = c;
        }
        floyd();
        int Min = INF*200, flag = 0;
        for(int i = 0; i < n; i++)
        {
            int sum = 0;
            for(int j = 0; j < n; j++)
            {
                sum += dis[i][j] + dis[j][i];
            }
 
            if(sum < Min) flag = i, Min = sum;
        }
 
        int temp[200];
        for(int i = 0; i < n; i++)
        {
            temp[i] = dis[flag][i] + dis[i][flag];
        }
 
        sort(temp,temp+n,greater());
 
        for(int i = 0 ; i < m; i++)
            Min -= temp[i];
        printf("Case %d:\n",Case++);
        Min > INF ? printf("No solution\n") : printf("%d\n",Min);
 
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved