title: 题目
德平在他的农场里养了n头牛，每头牛都有一个固定的位置,每天这些牛都要到德平家里参加聚会然后回去，给出n,m,代表牛数+1和有向边数,接着是m条有向边(a,b,c)，代表从牛a到牛b需要花费c秒，给你德平家的位置X（1~n的除x外的编号为牛的位置），每头牛都有一个参加聚会并且回到原来位置的最短时间，从这些最短时间里找出一个最大值输出 N<=1000,M<=100,000,c<=100
Line 1: 三个整数分别代表: _N_, _M_, and _X_
Lines 2.. _M_+1: Line _i_+1 代表道路i的三个整数：a,b,c
表示从a到b需要c时间,(不能表示从b到a的时间为c)
Line 1: 所有 牛最短时间里找出一个 最大值输出
牛1：去4s，回1s，共5s
牛3：去6s，回3s，共9s
牛4：去3s，回7s，共10s
title: 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
title: output
10
title: 思路
有n个节点, 其中一个节点是要去到的终点x。
在除x之外的节点中, 找到一个节点, 它去到x点的最短距离 + 从x点回来的最短距离, 之和的最大值。
我们可以求出所有点到x和x到所有点的最短距离, 然后遍历一遍结果求出最大值。
dijkstra可以求出从起点开始到所有点的最短路径, 模板是求从起点到终点, 这里把x点当做起点即可求出x到所有点的距离。
至于所有点到x的距离, 可以将所有的有向边反转方向, 再求一次dijkstra便是所有点到x的最短距离。
title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//------- Coding Area ---------//
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, m, x;
int dist[N], g[N][N];
int d1[N], d2[N];
bool st[N];
void dijkstra()
{
memset(dist, INF, sizeof dist);
memset(st, 0, sizeof st);
dist[x] = 0;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m >> x;
memset(g, INF, sizeof g);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
// 第一次
dijkstra();
memcpy(d1, dist, sizeof dist);
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
swap(g[i][j], g[j][i]);
}
// 第二次
dijkstra();
memcpy(d2, dist, sizeof dist);
int res = 0;
for (int i = 1; i <= n; i++)
res = max(d1[i] + d2[i], res);
cout << res << endl;
return 0 ;
}
~~~