CY-Left

CPPLeetCode基本功底开发语言

城市平乱

城市平乱

时间限制:1000 ms | 内存限制:65535 KB
难度:4

描述
南将军统领着N个部队,这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安,这M个城市分别编号从1到M。

现在,小工军师告诉南将军,第K号城市发生了暴乱,南将军从各个部队都派遣了一个分队沿最近路去往暴乱城市平乱。

现在已知在任意两个城市之间的路行军所需的时间,你作为南将军麾下最厉害的程序员,请你编写一个程序来告诉南将军第一个分队到达叛乱城市所需的时间。

注意,两个城市之间可能不只一条路。

输入
第一行输入一个整数T,表示测试数据的组数。(T<20)
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数,M表示城市数,P表示城市之间的路的条数,Q表示发生暴乱的城市编号。
随后的一行是N个整数,表示部队所在城市的编号。
再之后的P行,每行有三个正整数,a,b,t(1<=a,b<=M,1<=t<=100),表示a,b之间的路如果行军需要用时为t

数据保证暴乱的城市是可达的。
输出
对于每组测试数据,输出第一支部队到达叛乱城市时的时间。每组输出占一行
样例输入

1
3 8 9 8
1 2 3
1 2 1
2 3 2
1 4 2
2 5 3
3 6 2
4 7 1
5 7 3
5 8 2
6 8 2

样例输出

4

解题思路

弗洛伊德

#include <iostream>
#include <stdio.h>
using namespace std;
#define IF 100000000

struct cyMap
{
    int startPoint;
    int endPoint;
    int weight;
};

int main()
{
    int testNum = 0;
    scanf("%d", &testNum);
    while(testNum--){
        int armyAmount = 0;
        int city = 0;
        int road = 0; // P
        int war = 0; // Q
        scanf("%d%d%d%d", &armyAmount, &city, &road, &war);
        int armies[armyAmount];
        cyMap weightMap[road];

        // load army
        for(int i=0; i<armyAmount; i++) scanf("%d", &armies[i]);

        // load map
        for(int i=0; i<road; i++){scanf("%d%d%d", &weightMap[i].startPoint, &weightMap[i].endPoint, &weightMap[i].weight);}

        // excute army times freud
        int minWeight = IF;
        int lowestWay = IF;

        for(int freud = 0; freud<armyAmount; freud++){
            int currentCity[city];
            int preLen = 0; // 上一次最低权值
            for(int i=0; i<city; i++) currentCity[i] = IF;
            currentCity[armies[freud]-1] = 0;
            // 第一遍弗洛伊德
            int startCity = armies[freud];
            for(int i=0; i<city-1; i++)
            {
                // 开始工作 armies[freud]
                for(int j=0; j<road; j++)
                {
                    if(
                        weightMap[j].startPoint == startCity
                        && currentCity[weightMap[j].endPoint-1] !=0
                        && currentCity[weightMap[j].endPoint-1] > (weightMap[j].weight + preLen)
                    )
                    {
                        currentCity[weightMap[j].endPoint-1] = weightMap[j].weight + preLen;
                    }else if(
                        weightMap[j].endPoint == startCity
                        && currentCity[weightMap[j].startPoint-1] !=0
                        && currentCity[weightMap[j].startPoint-1] > (weightMap[j].weight + preLen)
                    )
                    {
                        currentCity[weightMap[j].startPoint-1] = weightMap[j].weight + preLen;
                    }
                }
                //for(int x=0; x<city; x++){cout<<currentCity[x]<<" ";}cout<<endl;
                // find lowest time
                int lowIndex = -1;
                int lowWeight = IF;
                // 返回最小的权值
                for(int k=0; k<city; k++){
                    if(currentCity[k]!=0 && currentCity[k] < lowWeight)
                    {
                        lowIndex = k;
                        lowWeight = currentCity[k];
                    }
                }
                preLen = lowWeight;
                currentCity[lowIndex] = 0;
                startCity = lowIndex+1;
                if(startCity==war) break;
                //cout<<"start city is:"<<lowIndex<<" , "<<currentCity[lowIndex]<<" "<<lowWeight<<endl;
            }
            if(preLen<lowestWay) lowestWay = preLen;
        }
        // return min;
        printf("%d\n", lowestWay);
    }
    return 0;
}
/**
1
3 8 9 8
1 2 3
1 2 1
2 3 2
1 4 2
2 5 3
3 6 2
4 7 1
5 7 3
5 8 2
6 8 2

**/

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=754