$$\color{Purple}{kuangbin题解目录}$$
描述
$N$ 头牛要去参加在某农场举行的一场编号为 $X$ 的牛的派对。
有 $M$ 条有向道路,每条路长 $T_i$;每头牛参加完派对后都必须回到家,每头牛都会选择最短路径。
求这 $N$ 头牛的最短路径(一个来回)中最长的一条的长度。
特别提醒:可能有权值不同的重边。
输入格式
第一行包含三个整数 $N,M,X$。
接下来 $M$ 行,每行包含三个整数 $A_i,B_i,T_i$,表示有一条从 $A_i$ 到 $B_i$ 的路,长度为 $T_i$。
输出格式
共一行,一个数,表示最短路中最长的一条的长度。
数据范围
$1 \\le N \\le 1000$,
$1 \\le X \\le N$,
$1 \\le M \\le 10^5$,
$1 \\le T_i \\le 100$
输入样例:
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
输出样例:
10
思路
- 注意该题图是
有向图
,若为无向图
,结果应为终点到每个点的最短距离*2
(从每个点求到终点的效率不高,故反向求的效果会更好);- 在有向图中,
回家
部分,即可看作从终点出发到每个点的最短距离,但是启程
部分,由于是从每个点出发到达终点,直接跑的时间复杂度相当于跑了$n$次最短路,相当不可取,但是可通过将边反转(反向建图)
,即可又转化为从终点出发到每个点的最短距离,时间复杂度直接降到最低;- 最后枚举$n$个点
启程最短
和回家最短
两部分和的最大值,即可解决该题.
代码
// Problem: 农场派对
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1134/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-24 20:47:25
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1010
#define MAXM 200010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int n,m,x;
int head[2][MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
int dist[2][MAXN];
int vis[MAXN];
void add(int op,int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[op][a];
head[op][a]=idx++;
}
void dijkstra(int start,int op)
{
memset(dist[op],0x3f,sizeof(dist[op]));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,start});
dist[op][start]=0;
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[op][temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[op][j]>temp_dis+val[i])
{
dist[op][j]=temp_dis+val[i];
q.push({dist[op][j],j});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> m >> x;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(0,a,b,c);//正向建边(求终点到每个点的距离)——回家
add(1,b,a,c);//反向建边(求每个点到终点的距离)——启程
}
dijkstra(x,0);
dijkstra(x,1);
int res=0;
for(int i=1;i<=n;i++)
res=max(res,dist[0][i]+dist[1][i]);
cout << res << endl;
return 0;
}