[SOJ] 导游

时间：2020-12-21 20:25:37
Description

Mr. G. 在孟加拉国的一家旅游公司工作。他当前的任务是带一些游客去一些遥远的城市。和所有国家一样，一些城市之间有双向道路。每对相邻城市之间都有一条公交路线，每条路线都规定了自己的最大乘客数目。Mr. G. 有一份包含城市间道路状况和公交车最大载客量的地图。
往往无法一次性地将所有乘客带往目的地。例如，在下面7个城市的地图中，边代表道路，每条边上的数字代表这条道路上公交车的最大载客量。
[SOJ] 导游
如果Mr. G. 要将99位乘客从城市1带到城市7，则至少要往返5次（他必须陪同每一群乘客）。最佳路线是1-2-4-7。

初始： 1（99） 2（0） 4（0） 7（0）

第1次往返后：1(75) 2(0) 4(0) 7(24)

第2次往返后：1(51) 2(0) 4(0) 7(48)

第3次往返后：1(27) 2(0) 4(0) 7(72)

第4次往返后：1(3) 2(0) 4(0) 7(96)

第5次往返后：1(0) 2(0) 4(0) 7(99)

Input

第一行为一个整数t，表示测试用例个数。 每组数据的第一行有两个整数N(N≤100)和R(R≤4950)，分别表示城市的数量和道路的数量。接下来的R行每行有3个整数（C1,C2,P），其中C1和C2为城市编号，P(1<P<10000)是该道路上公交车的最大载客量。各城市编号为1~N的连续整数。第R+1行包含3个整数（S,D,T），分别表示出发城市，目的城市的编号和游客的数量(1<T<100000)。保证两个城市间最多只有一条道路。

Output

对于每组输入数据，输出最少的往返次数。

Sample Input
[SOJ] 导游 Copy sample input to clipboard
1

7 10

1 2 30

1 3 15

1 4 10

2 4 25

2 5 60

3 4 40

3 6 20

4 7 35

5 7 20

6 7 30

1 7 99
Sample Output
5

#include<iostream>

#include<algorithm>

using namespace std;

const int MAX = 105;

const int INF = -1;

int n, r;

int edge[MAX][MAX];

void init()

{

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

  {

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

      edge[i][j]=INF;

    edge[i][i]=0;

  }

}

int main()

{

  int t;

  cin>>t;

  while(t--)

  {

    cin>>n>>r;

    int a, b, x;

    init();

    for(int i=0;i<r;i++)

    {

      cin>>a>>b>>x;

      edge[a][b]=x;

      edge[b][a]=x;

    }

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

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

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

        {

           edge[i][j]=max(edge[i][j],min(edge[i][k], edge[k][j]));

        }

    int s, e, p;

    cin>>s>>e>>p;

    cout<<p/(edge[s][e]-1)+(p%edge[s][e]?1:0)<<endl;

  }

  return 0;

}

　　

相关文章