1992 聚会

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

小S 想要从某地出发去同学k的家中参加一个party，但要有去有回。他想让所用的
时间尽量的短。但他又想知道从不同的点出发，来回的最短时间中最长的时间是多
少，这个任务就交给了你

输入描述 Input Description

第一行三个正整数n, m, k(n是节点个数，m是有向边的条数，k是参加聚会的地点
编号)( 1 ≤ n ≤ 1000 ,1 ≤ m ≤ 100,000)
第二行..m + 1行每行3个整数x，y，w 代表从x到y需要花w的时间 0<w<=100

输出描述 Output Description

输出从不同的节点出发的最短时间中最长的时间

样例输入 Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN = 1010;
 7 
 8 struct Edge{
 9     int to,w,nxt;
10 }e[100100];
11 
12 int dis[MAXN];
13 int diss[MAXN];
14 int head[MAXN];
15 bool vis[MAXN];
16 queue<int>q;
17 int n,m,k,cnt,ans;
18 
19 void add(int u,int v,int w)    //从u到v有一条长度是w的边 
20 {
21     ++cnt;
22     e[cnt].to = v;
23     e[cnt].w = w;
24     e[cnt].nxt = head[u];
25     head[u] = cnt;
26 }
27 
28 void spfa(int k)
29 {
30     memset(dis,0x3f,sizeof(dis));
31     memset(vis,0,sizeof(vis));
32     while (!q.empty()) q.pop();
33     dis[k] = 0;
34     q.push(k);
35     vis[k] = true;
36     while (!q.empty())
37     {
38         int u = q.front();
39         q.pop();
40         for (int i=head[u]; i; i=e[i].nxt)
41         {
42             int v = e[i].to;
43             int w = e[i].w;
44             if (dis[v]>dis[u]+w)
45             {
46                 dis[v] = dis[u]+w;
47                 if (!vis[v])
48                 {
49                     q.push(v);
50                     vis[v] = true;
51                 }
52             }
53         }
54         vis[u] = false;
55     }
56 }
57 
58 int main()
59 {
60     scanf("%d%d%d",&n,&m,&k);
61     for (int u,v,w,i=1; i<=m; ++i)
62     {
63         scanf("%d%d%d",&u,&v,&w);
64         add(u,v,w);
65     }
66     spfa(k);
67     for (int i=1; i<=n; ++i)
68         diss[i] = dis[i];
69     for (int i=1; i<=n; ++i)
70     {
71         if (i!=k) spfa(i);
72         if (dis[k]<=10000000 && diss[i]<=10000000)ans = max(ans,dis[k]+diss[i]);
73     }
74     printf("%d",ans);
75     return 0;
76 }