微信官方网站下载安装,ps设计师网站有哪些,郴州网站设计,迁安建设局官方网站题目描述 WFYZ的校园很大#xff0c;这里生活着很多生物#xff0c;比如住在钟楼上的的鸽子#xff0c;其中鸽子冉冉和她的妹妹凝凝白天在不同的地方吃虫#xff0c;而在晚上她们都回到钟楼休息。她俩是两只懒鸟#xff0c;于是提出了一个计划#xff0c;尽量减少她们在飞…题目描述 WFYZ的校园很大这里生活着很多生物比如住在钟楼上的的鸽子其中鸽子冉冉和她的妹妹凝凝白天在不同的地方吃虫而在晚上她们都回到钟楼休息。她俩是两只懒鸟于是提出了一个计划尽量减少她们在飞行时花费的总能量。当从一个区域飞到邻近区域时冉冉花费R个能量单位凝凝花费S个能量单位。然而如果冉冉和凝凝在同一个区域时冉冉可以背着凝凝飞而只消耗P个能量单位其中P可能远远小于R S。如果P非常小最节能的解决方案可能是冉冉和凝凝前往一个区域然后冉冉背着凝凝飞回钟楼。当然如果P很大那么冉冉和凝凝可能各自飞。给定RS和P以及校园的布局请计算冉冉和凝凝到达谷仓所需的最低能量。 输入 第一行输入包含正整数RSPN和M. (RSPN,M40,000)。RS和P如上所述。 N是校园中的区域数编号为1..N其中N 3有M条飞行线路。冉冉和凝凝分别从1区和2区开始。钟楼在N区.以下输入M行代表两个区域的有飞行路线。连接是双向的。总是可以沿着一系列这样的连接从场1到场N场2到场N。 输出 一个整数冉冉和凝凝集体到达钟楼需要花费的最小能量。 样例输入 复制样例数据 4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8样例输出 22提示 在例子中冉冉从1到4凝凝从2到3到4然后他们一起旅行从4到7到8。【数据规模与约定】对于20%的数据1≤N≤5001≤M≤2000。对于100%的数据1≤N≤400001≤M≤40000。 思路 跑三遍最短路分别是两个人啊两只鸽子分别飞到钟楼的花费还有就是从钟楼到各个区域的最短路然后枚举会合点 1 #include iostream2 #include bits/stdc.h3 using namespace std;4 typedef long long ll;5 const int maxn 4e450;6 int sum0;7 int tot,r,s,p,n,m;8 int head[maxn*2],ver[maxn*2],edge[maxn*2],Next[maxn*2],d[maxn*2];9 bool v[maxn*2];
10 int len1[maxn],len2[maxn],len3[maxn];
11 queueint q;
12 void add(int x,int y,int z)
13 {
14 ver[tot]y;
15 edge[tot]z;
16 Next[tot]head[x];
17 head[x]tot;
18 }
19 void spfa(int t)
20 {
21 memset(d,0x3f,sizeof(d));
22 memset(v,0,sizeof(v));
23 d[t]0;
24 v[t]1;
25 q.push(t);
26 while(q.size())
27 {
28 int xq.front();
29 q.pop();
30 v[x]0;
31 for(int ihead[x];i;iNext[i])
32 {
33 int yver[i],zedge[i];
34 if(d[y]d[x]z)
35 {
36 d[y]d[x]z;
37 if(!v[y])
38 {
39 q.push(y),v[y]1;
40 }
41 }
42 }
43 }
44 }
45 int main()
46 {
47 scanf(%d%d%d%d%d,r,s,p,n,m);
48 for(register int i1;im;i)
49 {
50 int x,y;
51 scanf(%d%d,x,y);
52 add(x,y,1);
53 add(y,x,1);
54 }
55 spfa(1);
56 for(register int i1;in;i)
57 {
58 len1[i]d[i];
59 }
60 int t1d[n];
61 spfa(2);
62 for(register int i1;in;i)
63 {
64 len2[i]d[i];
65 }
66 int t2d[n];
67 int resr*t1s*t2;
68 spfa(n);
69 for(register int i1;in;i)
70 {
71 len3[i]d[i];
72 }
73 for(register int i1;in;i)
74 {
75 int temp1r*len1[i]s*len2[i];
76 int temp2p*len3[i];
77 resmin(res,temp1temp2);
78 }
79 printf(%d\n,res);
80 //cout Hello world! endl;
81 return 0;
82 } View Code 转载于:https://www.cnblogs.com/SoulSecret/p/10304510.html
