NYNU_省赛选拔题(5)

题目描述

P 的一家要出去旅游，买了当地的地图，发现各地分别由各个景点，若 P 想使家人分队去景点，尽快到达各个景点(必须所有景点)，并且最终所有家人都到达 M 所在的景点.   
你用程序告诉 P 最少需要多少天才能完成这次旅游。假设 P 的家人足够多，各分队速度一样.

输入

首先是一个正整数T，接下来是T组测试数据，每组数据第一行是两个整数n,m(2=<n<=1000,1=<m<=10000)，分别表示景点数量和总边数，山寨编号0，1，2，3…n-1
接下来m行，每行三个整数i,j,k(0=<i,j<n,k<=10^4)，分别表示景点i和景点j之间有一条路，在这条路上需要k天，接下来一行两个整数s,t(0<=s,t<=n-1)，分别表示P所在的起点和M所在终点的编号

输出

对每组数据输出一个整数，表示P到达所有山寨并汇聚到M所在景点所需要的最少天数，每个输出独占一行

样例输入

2

5 6

0 1 1

1 2 3

3 1 2

4 0 3

3 2 3

3 4 1

4 3

5 5

1 0 2

1 2 4

1 3 3

4 2 1

3 4 2

4 2

样例输出

7

13

求出所有点到起点，终点最短路权值，然后相加取最大，dijkstra算法

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <cmath>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define Max 1001

 int cost[Max][Max];

 int d[Max];

 bool used[Max];

 void dijkstra(int n,int s)

 {

     memset(d,INF,sizeof(d));

     memset(used,false,sizeof(used));

     d[s]=;

     while(true)

     {

         int v=-;

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

             if(!used[u]&&(v==-||d[u]<d[v]))

                 v=u;

         if(v==-)

             break;

         used[v]=true;

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

         {

             d[u]=min(d[u],d[v]+cost[u][v]);

         }

     }

 }

 int main()

 {

     int T,m,n,k,i,j;

     int from,to,Cost,f,t;

     cin>>T;

     while(T--)

     {

         memset(cost,INF,sizeof(cost));

         cin>>n>>m;

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

         {

             cin>>from>>to>>Cost;

             cost[from][to]=cost[to][from]=Cost;

         }

         cin>>f>>t;

         dijkstra(n,f);

         int Time[Max],tim=;

         memset(Time,,sizeof(Time));

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

             Time[i]=d[i];

         dijkstra(n,t);

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

         {

             Time[i]+=d[i];

             tim=max(tim,Time[i]);

         }

         cout<<tim<<endl;

     }

 }