题目描述

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; }
}
05-08 15:41