PTA xt的考研路 往返 最短路

xt是我院19级专业第一，但他认为保研并不能展示他全部的实力，所以他在22年初试一结束就加入了23考研的队伍中，并且他为了填补我院近些年来无北大研究生的空白，毅然决然决定扛起19级的大旗，在学校百年华诞之际献上他最诚挚的礼物。

xt每天都游走在寝室，食堂和图书馆，三点一线，即便是在疫情局势蔓延的形势下，凌晨三点半刚做完核酸，他六点半还是照常起来卷。现在他太忙了，好像在提前准备复试了，想让你帮个小忙，xt会给出学校的地图(有向图)，并且给出寝室，食堂和图书馆的编号(编号从0开始)，希望你从该图中找出一个子图，要使得在这个子图中，寝室能够到达图书馆，食堂也能到达图书馆，同时希望在这个子图中的所有边的边权之和最小。如果你找不到任何一个子图符合要求的话()，输出“xt,我好没本领！”，因为你找不到并不代表xt找不到

子图的定义：

 从原图中删去一些点或删去一些线或既删去一些点又删去一些线，剩下的部分（当然必须仍然是图）。允许两种极端情况：什么都不删；删去所有点和所有线。

输入格式:

第一行输入点的个数 n，3 <= n <= 105，边的个数 m，0 <= m <= 2∗105

第二行给出寝室的编号id1，食堂的编号id2，图书馆的编号id3，题目保证三个编号两两不同。

随后 m 行按照以下形式描述边，表示有一条有向边，起点是from，终点是to，权值是w

from to w

 0 <= from, to <= n - 1，from != to，1 <= w <= 10^9

输出格式1:

如果子图存在则输出最小边权和，如果不存在输出“xt,我好没本领！”

输入样例1:

6 9
0 1 5
0 2 2 
0 5 6 
1 0 3 
1 4 5 
2 1 1 
2 3 3 
2 3 4 
3 4 2 
4 5 1

输出样例1:

9

解释：

上图为输入的图。

蓝色边为最优子图之一。

注意，直接选择0 1 5三点构成的子图也能得到最优解，但无法在满足所有限制的前提下，得到更优解。

输入样例2:

3 2
0 1 2
0 1 1
2 1 1

输出样例2:

xt,我好没本领！

解释：

上图为输入的图。

可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。

 思路：

       1.跑以寝室，食堂为起点的最短路，存入d_1， d_2 。

       2.跑以图书馆为起点的反向最短路，存入d_3。

       3.便历从0->n所有点，以d_1[i] + d_2[i] + d_3[i]  为所有点到这个点的路径长度，

一直取其最小（ans=min（d_1[i] + d_2[i] + d_3[i]，ans）。

如果未改变，就按题目要求输出，改变了就输出ans；

代码：

#include
using namespace std;
#define ll long long
#define pli pair
ll n , m , k , idx , cnt;
const ll inf = 0x3f3f3f3f3f3f/3;
const int l = 200005;
const int r = 100005;
int ne_12[l] , e_12[l] , h_12[l] ;
int ne_3 [l] , e_3 [l] , h_3 [l] ;
ll d_1[r] , d_2[r] , d_3[r] , dist_12[r] , w_12[l] , w_3 [l];
bool st[r];
void add(int a,int b,int c){ne_12[idx] = h_12[a];e_12[idx] = b;w_12[idx] = c;h_12[a] = idx ++;
/*QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ QWQ*/ne_3[cnt] = h_3[b];e_3[cnt] = a;w_3[cnt] = c;h_3[b] = cnt ++;
}
void bfs_12(int x){memset(st , 0 ,sizeof st);for(int i = 0 ; i < n ; i ++)dist_12[i] = inf;priority_queue,greater >q;q.push({0,x}); dist_12[x] = 0;while(!q.empty()){int t = q.top().second;q.pop();if(st[t])continue;st[t] = 1;for(int i = h_12[t] ; i != -1 ; i = ne_12[i]){int to = e_12[i];if(dist_12[to] <= dist_12[t] + w_12[i])continue;dist_12[to] = dist_12[t] + w_12[i];q.push({dist_12[to],to});}}
}
void bfs_3(int x){memset(st , 0 , sizeof st);for(int i = 0 ; i < n ; i ++)d_3[i] = inf;priority_queue,greater >q;q.push({0,x});d_3[x] = 0;while(!q.empty()){int t = q.top().second;q.pop();if(st[t])continue;st[t] = 1;for(int i = h_3[t] ; i != -1 ; i = ne_3[i]){int to = e_3[i];if(d_3[to] <= d_3[t] + w_3[i])continue;d_3[to] = d_3[t] + w_3[i];q.push({d_3[to],to});}}
}
int main(){int qs , st , tsg;cin >> n >> m;cin >> qs >> st >> tsg;idx = cnt = 0;memset(h_3 , -1 , sizeof h_3);memset(h_12 , -1 , sizeof h_12);while(m --){int a , b , c;cin >> a >> b >> c;add(a,b,c);}bfs_12(st);for(int i = 0 ; i < n ; i ++)d_1[i] = dist_12[i];bfs_12(qs);for(int i = 0 ; i < n ; i ++)d_2[i] = dist_12[i];bfs_3(tsg);ll ans = inf;for(int i = 0 ; i < n ; i ++){if(d_1[i] >= inf || d_2[i] >= inf || d_3[i] >= inf|| d_1[i] < 0 || d_2[i] < 0 || d_3[i] < 0)continue;ans = min(ans,d_1[i]+d_2[i]+d_3[i]); }if(ans >= inf)cout << "xt,我好没本领！\n";else cout << ans << endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！