CodeForces 189D(最短路+dp)

我不是女神ヾ 2022-06-02 05:09 166阅读 0赞

问题描述:

PMP is getting a warrior. He is practicing a lot, but the results are not acceptable yet. This time instead of programming contests, he decided to compete in a car racing to increase the spirit of victory. He decides to choose a competition that also exhibits algorithmic features.

AlgoRace is a special league of car racing where different teams compete in a country of n cities. Cities are numbered 1 through n. Every two distinct cities in the country are connected with one bidirectional road. Each competing team should introduce one driver and a set of cars.

The competition is held in r rounds. In i\-th round, drivers will start at city siand finish at city ti. Drivers are allowed to change their cars at most ki times. Changing cars can take place in any city in no time. One car can be used multiple times in one round, but total number of changes should not exceed ki. Drivers can freely choose their path to destination.

PMP has prepared m type of purpose-built cars. Beside for PMP’s driving skills, depending on properties of the car and the road, a car traverses each road in each direction in different times.

PMP Warriors wants to devise best strategies of choosing car and roads in each round to maximize the chance of winning the cup. For each round they want to find the minimum time required to finish it.

Input

The first line contains three space-separated integers n, m, r (2 ≤ n ≤ 60, 1 ≤ m ≤ 60, 1 ≤ r ≤ 105) — the number of cities, the number of different types of cars and the number of rounds in the competition, correspondingly.

Next m sets of n × n matrices of integers between 0 to 106 (inclusive) will follow — describing the time one car requires to traverse different roads. The k\-th integer in j\-th line of the i\-th set is the time that i\-th car requires to traverse the road from j\-th city to k\-th city. These matrices are not necessarily symmetric, but their diagonal is always zero.

Next r lines contain description of the rounds. The i\-th of these lines contains space-separated integers si, ti, ki (1 ≤ si, ti ≤ n, si ≠ ti, 0 ≤ ki ≤ 1000) — the number of starting city, finishing city and the number of possible car changes in i\-th round, correspondingly.

Output

For each round you should print the minimum required time to complete the round in a single line.

Input

4 2 3
    0 1 5 6
    2 0 3 6
    1 3 0 1
    6 6 7 0
    0 3 5 6
    2 0 1 6
    1 3 0 2
    6 6 7 0
    1 4 2
    1 4 1
    1 4 3

Output

3
    4
    3

Input

4 2 3
    0 7 3 3
    8 0 10 5
    1 1 0 4
    8 9 2 0
    0 3 3 9
    7 0 4 9
    3 8 0 4
    4 8 9 0
    2 3 3
    2 1 3
    1 2 2

Output

4
    5
    3

题目题意:题目给了好几种车的，每种车从a到b的距离都不同，r次查询从s到e最多换车k车，问每次需要的最短时间

题目分析:先最短路跑出每种车俩点之间的最短时间，然后保存从i到j的最短时间（不同车之间比较）。dp\[k\]\[i\]\[j\]保存的是换车小于等于k次从i到j的最短时间.

代码如下:

#include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const int maxn=65;
    int G[maxn][maxn][maxn],dp[maxn][maxn][maxn];
    
    int main()
    {
        int n,m,r;
        while (scanf("%d%d%d",&n,&m,&r)!=EOF) {
            for (int k=1;k<=m;k++) {
                for (int i=1;i<=n;i++) {
                    for (int j=1;j<=n;j++) {
                        scanf("%d",&G[k][i][j]);
                    }
                }
            }
            for (int l=1;l<=m;l++) {
                for (int k=1;k<=n;k++) {
                    for (int i=1;i<=n;i++) {
                        for (int j=1;j<=n;j++) {
                            G[l][i][j]=min(G[l][i][j],G[l][i][k]+G[l][k][j]);
                        }
                    }
                }
            }
            for (int k=0;k<=n;k++) {
                for (int i=1;i<=n;i++) {
                    for (int j=1;j<=n;j++) {
                        dp[k][i][j]=inf;
                    }
                }
            }
            for (int l=1;l<=m;l++) {
                for (int k=1;k<=n;k++) {
                    for (int i=1;i<=n;i++) {
                        for (int j=1;j<=n;j++) {
                            dp[0][i][j]=min(dp[0][i][j],G[l][i][k]+G[l][k][j]);//保存a到b的最短时间
                        }
                    }
                }
            }
            for (int l=1;l<=n;l++) {
                for (int k=1;k<=n;k++) {
                    for (int i=1;i<=n;i++) {
                        for (int j=1;j<=n;j++) {
                            dp[l][i][j]=min(dp[l][i][j],dp[l-1][i][k]+dp[0][k][j]);
                        }
                    }
                }
            }
            while (r--) {
                int s,e,k;
                scanf("%d%d%d",&s,&e,&k);
                int ans=inf;
                k=min(k,n);
                for (int i=0;i<=k;i++) ans=min(ans,dp[i][s][e]);
                printf("%d\n",ans);
            }
        }
        return 0;
    }