图灵杯 蔡老板的会议

题目描述

图灵杯个人赛就要开始了，蔡老板召集俱乐部各部门的部长开会。综合楼有N (1<=N<=1000)间办公室，编号1~N每个办公室有一个部长在工（mo）作（yu），其中X号是蔡老板的办公室，会议也将在X(1<=X<=N)号办公室举行。综合楼的构造极其特殊，这N个办公室之间M(1<=M<=100,000)条单向走廊。通过第i条路将需要花费Ti(1<=Ti<=100)单位时间。

由于工作很忙，开完会之后各部长需要返回自己的办公室。他们会选择最短时间的最优路径。

为了合理安排接下来的工作，蔡老板想知道，【来回最久的】【！！！】那个部长在路上花费的时间是多少。

输入

第一行：用空格隔开的三个数N，M和X

接下来的M行：每行有用空格隔开的三个数Ai，Bi和Ti，表示从A点到B点花费的时间Ti

输出

一个int型的数，表示花费时间的最大值

样例输入

4 4 1

1 2 1

2 3 1

3 4 3

4 1 3

样例输出

8

题目开始真的是gay，最后才告诉我们是：来回最久的！！！看来理解题意很重要。

思路：先求x到所以点i的最短路 dx[i], 然后再求所以点到 x 的最短路（把路径反过来，求x到i的最短路），两者和最大就是答案了。

#include <iostream>#include<stdio.h>#include<string.h>#define siz 1005#define inf 9999999using namespace std;long long int gx[siz][siz],gy[siz][siz];long long int dx[siz],dy[siz];int vis[siz];int n,m,x;int main(){int a,b,t;while(scanf("%d %d %d",&n,&m,&x)!=EOF){memset(vis,0,sizeof(vis));for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)gx[i][j]=gy[i][j]=inf;//gx[i][i]=gy[i][i]=0;}for(int i=1;i<=m;i++){scanf("%d %d %d",&a,&b,&t);if(gx[a][b]>t) gx[a][b]=t;if(gy[b][a]>t) gy[b][a]=t;}for(int i=1;i<=n;i++) dx[i]=gx[x][i];vis[x]=1, dx[x]=0;while(1){int v=-1,mx=inf;for(int i=1;i<=n;i++){if(!vis[i]&&dx[i]<mx) mx=dx[i], v=i;}if(v==-1) break;vis[v]=1;for(int i=1;i<=n;i++){if(!vis[i]&&dx[i]>dx[v]+gx[v][i])dx[i]=dx[v]+gx[v][i];}}///--------------------------memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dy[i]=gy[x][i];vis[x]=1, dy[x]=0;while(1){int v=-1, mx=inf;for(int i=1;i<=n;i++){if(!vis[i]&&dy[i]<mx) mx=dy[i], v=i;}if(v==-1) break;vis[v]=1;for(int i=1;i<=n;i++){if(!vis[i]&&dy[i]>gy[v][i]+dy[v])dy[i]=gy[v][i]+dy[v];}}int ans=-9999;for(int i=1;i<=n;i++){if(ans<dx[i]+dy[i]) ans=dx[i]+dy[i];}cout<<ans<<endl;}return 0;}