开网站建设公司好,公司名高端大气不重名,设计一个商务网站,长沙公司网站建立文章目录 [USACO10FEB] Chocolate Giving S题面翻译题目描述输入格式输出格式 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题意解析CODE给点思考 [USACO10FEB] Chocolate Giving S
题面翻译
题目链接#xff1a;https://www.luogu.com.cn/problem/P2984
题目描… 文章目录 [USACO10FEB] Chocolate Giving S题面翻译题目描述输入格式输出格式 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题意解析CODE给点思考 [USACO10FEB] Chocolate Giving S
题面翻译
题目链接https://www.luogu.com.cn/problem/P2984
题目描述
FJ 有 B B B 头奶牛 ( 1 ≤ B ≤ 25000 ) (1\le B\le 25000) (1≤B≤25000)有 N ( 2 × B ≤ N ≤ 50000 ) N(2\times B\le N\le 50000) N(2×B≤N≤50000) 个农场编号 1 1 1 到 N N N有 M ( N − 1 ≤ M ≤ 100000 ) M(N-1\le M\le 100000) M(N−1≤M≤100000) 条双向边第 i i i 条边连接农场 R i R_i Ri 和 S i ( 1 ≤ R i ≤ N , 1 ≤ S i ≤ N ) S_i(1\le R_i\le N, 1\le S_i\le N) Si(1≤Ri≤N,1≤Si≤N)该边的长度是 L i ( 1 ≤ L i ≤ 2000 ) L_i(1\le L_i\le 2000) Li(1≤Li≤2000)。居住在农场 P i P_i Pi 的奶牛 A ( 1 ≤ P i ≤ N ) (1\le P_i\le N) (1≤Pi≤N)想送一份新年礼物给居住在农场 Q i ( 1 ≤ Q i ≤ N ) Q_i(1\le Q_i\le N) Qi(1≤Qi≤N) 的奶牛 B但是奶牛 A 必须先到 FJ居住在编号 1 1 1 的农场那里取礼物然后再送给奶牛 B。你的任务是奶牛 A 至少需要走多远的路程
输入格式 第一行三个整数 N , M , B N,M,B N,M,B。 第 2 2 2 至 M 1 M1 M1 行每行 3 3 3 个整数 R i , S i , L i R_i,S_i,L_i Ri,Si,Li。 第 M 2 M2 M2 至 M B 1 MB1 MB1 行进行 B B B 次询问每行 2 2 2 个整数 P i , Q i P_i ,Q_i Pi,Qi。
输出格式
每次询问输出一个整数即答案。
题目描述
Farmer John is distributing chocolates at the barn for Valentine’s day, and B (1 B 25,000) of his bulls have a special cow in mind to receive a chocolate gift.
Each of the bulls and cows is grazing alone in one of the farm’s N (2*B N 50,000) pastures conveniently numbered 1…N and connected by M (N-1 M 100,000) bidirectional cowpaths of various lengths. Some pastures might be directly connected by more than one cowpath. Cowpath i connects pastures R_i and S_i (1 R_i N; 1 S_i N) and has length L_i (1 L_i 2,000).
Bull i resides in pasture P_i (1 P_i N) and wishes to give a chocolate to the cow in pasture Q_i (1 Q_i N).
Help the bulls find the shortest path from their current pasture to the barn (which is located at pasture 1) and then onward to the pasture where their special cow is grazing. The barn connects, one way or another (potentially via other cowpaths and pastures) to every pasture.
As an example, consider a farm with 6 pastures, 6 paths, and 3 bulls (in pastures 2, 3, and 5) who wish to bestow chocolates on their love-objects:
*1 -- Bull wants chocolates for pasture 1 cow[4]--3--[5] -- [5] is the pasture ID/ |/ |4 2 -- 2 is the cowpath length/ | between [3] and [4][1]--1--[3]*6/ \ /9 3 2/ \/[6] [2]*4* The Bull in pasture 2 can travel distance 3 (two different ways) to get to the barn then travel distance 21 to pastures [3] and [4] to gift his chocolate. That’s 6 altogether.
* The Bull in pasture 5 can travel to pasture 4 (distance 3), then pastures 3 and 1 (total: 3 2 1 6) to bestow his chocolate offer.
* The Bull in pasture 3 can travel distance 1 to pasture 1 and then take his chocolate 9 more to pasture 6, a total distance of 10.
输入格式
* Line 1: Three space separated integers: N, M, and B
* Lines 2…M1: Line i1 describes cowpath i with three
space-separated integers: R_i, S_i, and L_i
* Lines M2…MB1: Line Mi1 contains two space separated integers: P_i and Q_i
输出格式
* Lines 1…B: Line i should contain a single integer, the smallest distance that the bull in pasture P_i must travel to get chocolates from the barn and then award them to the cow of his dreams in pasture Q_i
样例 #1
样例输入 #1
6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2 4
5 1
3 6样例输出 #1
6
6
10题意解析
找一个点先到 1 1 1 号点的最短距离再找 1 1 1 号点到另一点的最短距离求两者之和。乍一看以为是 F l o y d Floyd Floyd 算法但是一看数据范围很大那就并不是了那还有什么算法能解决这种最短路问题呢其实这并不是多源最短路问题因为是双向图所以你到我的最短路其实也是我到你的最短路所以这题就变成了 1 1 1 号点到另外两个点的最短路之和的问题了其实是单源最短路问题。考虑到 D i j k s t r a Dijkstra Dijkstra 可能超时所以用 S P F A SPFA SPFA CODE
#include iostream
#include vector
#include cstring
#include algorithm
#include queue
#define ll long long
#define INF 0x3f3f3f3f using namespace std;typedef pairint, int pii;const int N 50050, M 2e5 10;
int h[N], e[M], ne[M], w[M], idx; // 定义图的存储结构
int dist[N]; // 存储每个节点到源点的最短距离
bool st[N]; // 存储每个节点是否在队列中
int n, m, b; // n是节点数m是边的数目b是查询的数目// 添加一条边
void add(int a, int b, int c){e[idx] b; // 边的终点ne[idx] h[a]; // 下一条相同起点的边w[idx] c; // 边的权重h[a] idx; // 更新起点a的最后一条边
}// SPFA算法用于求解单源最短路径
void spfa(){memset(dist, INF, sizeof dist); // 初始化所有节点到源点的距离为无穷大dist[1] 0; // 源点到自己的距离为0queueint q;q.push(1); // 将源点加入队列st[1] true; // 标记源点已经在队列中while(q.size()){auto t q.front(); // 取出队首元素q.pop();st[t] false; // 标记t已经不在队列中for(int i h[t]; i ! -1; i ne[i]){ // 遍历所有从t出发的边int j e[i];if(dist[j] dist[t] w[i]){ // 如果可以通过t到j的距离小于当前的最短距离dist[j] dist[t] w[i]; // 更新最短距离if(!st[j]){ // 如果j不在队列中q.push(j); // 将j加入队列st[j] true; // 标记j已经在队列中}}}}
}int main()
{memset(h, -1, sizeof h); // 初始化邻接表cin n m b; // 输入节点数边的数目查询的数目while(m--){int a, b, c;scanf(%d%d%d, a, b, c); // 输入边的信息add(a, b, c), add(b, a, c); // 将边添加到图中}spfa(); // 执行SPFA算法求解最短路径while(b--){int p, q;scanf(%d%d, p, q); // 输入查询cout dist[p] dist[q] endl; // 输出结果}
} 给点思考
为什么边权数组不用初始化为 I N F INF INF 因为只有在遍历队列首元素t的所有出边时才会用到w[i]所以能用到肯定存在所以不需要初始化。 无向图该注意的问题 边数应该开两倍因为无向开少了就RE。
