做网站制作要多少费用,手机网站 侧边栏导航,免费域名映射,学历网站怎么做xt是我院19级专业第一#xff0c;但他认为保研并不能展示他全部的实力#xff0c;所以他在22年初试一结束就加入了23考研的队伍中#xff0c;并且他为了填补我院近些年来无北大研究生的空白#xff0c;毅然决然决定扛起19级的大旗#xff0c;在学校百年华诞之际献上他最诚…xt是我院19级专业第一但他认为保研并不能展示他全部的实力所以他在22年初试一结束就加入了23考研的队伍中并且他为了填补我院近些年来无北大研究生的空白毅然决然决定扛起19级的大旗在学校百年华诞之际献上他最诚挚的礼物。 xt每天都游走在寝室食堂和图书馆三点一线即便是在疫情局势蔓延的形势下凌晨三点半刚做完核酸他六点半还是照常起来卷。现在他太忙了好像在提前准备复试了想让你帮个小忙xt会给出学校的地图(有向图)并且给出寝室食堂和图书馆的编号(编号从0开始)希望你从该图中找出一个子图要使得在这个子图中寝室能够到达图书馆食堂也能到达图书馆同时希望在这个子图中的所有边的边权之和最小。如果你找不到任何一个子图符合要求的话()输出“xt,我好没本领”因为你找不到并不代表xt找不到
子图的定义 从原图中删去一些点或删去一些线或既删去一些点又删去一些线剩下的部分当然必须仍然是图。允许两种极端情况什么都不删删去所有点和所有线。 输入格式:
第一行输入点的个数 n3 n 105边的个数 m0 m 2∗105
第二行给出寝室的编号id1食堂的编号id2图书馆的编号id3题目保证三个编号两两不同。
随后 m 行按照以下形式描述边表示有一条有向边起点是from终点是to权值是w
from to w0 from, to n - 1from ! to1 w 109
输出格式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 的路径所以不存在任何子图满足所有限制。 题目大意 求寝室和食堂到图书馆的最短路。 思路 跑三遍dijkstra分别从寝室和食堂跑一边正向路从图书馆跑一边反向路。 #includebits/stdc.h
using namespace std;
typedef int ll;
#define endl \n
#define P pairll,llconst ll N 1e57 ,M 2e57 ,MAX 0x3f3f3f3f3f3f3f3f/3;
ll n,m,now,nowf;//now为正向head初始点,nowf为反向head初始点
ll head[2][N],value[3][N],ne[2][M],e[2][M],v[2][M];//0记录反向路,1记录正向路 void add(ll x ,ll y ,ll z ,bool f){//用f判断路的方向 if(f)e[1][now] y ,ne[1][now] head[1][x] ,v[1][now] z ,head[1][x] now;else e[0][nowf] y ,ne[0][nowf] head[0][x] ,v[0][nowf] z ,head[0][x] nowf;
}void dj(ll x ,ll y ,ll z){priority_queueP,vectorP,greaterP q;q.push({0,x});value[y][x]0;while(!q.empty()){ll op q.top().second;q.pop();for(ll i head[z][op] ; ~i ; i ne[z][i]){ll to e[z][i] ,va v[z][i];if(value[y][to] value[y][op] va){value[y][to] value[y][op] va;q.push({value[y][to],to});}}}return;
}void solve(){memset(head,-1,sizeof head);memset(value,MAX,sizeof value);ll x,y,z,id1,id2,id3,mxMAX;now0,nowf0;cin n m id1 id2 id3;while(m--){cin x y z;add(x,y,z,1),add(y,x,z,0);}dj(id1,1,1),dj(id2,2,1),dj(id3,0,0);for(ll i 0 ; i n ; i )mx min(mx , value[0][i] value[2][i] value[1][i]);mx MAX ? cout mx endl : cout xt,我好没本领 endl;return;
}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;//cin t;while(t --)solve();return 0;
}
