洛谷——P2984 [USACO10FEB]给巧克力Chocolate Giving
https://www.luogu.org/problem/show?pid=2984
题目描述
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 2+1 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.
Farmer John有B头奶牛(1<=B<=25000),有N(2*B<=N<=50000)个农场,编号1-N,有M(N-1<=M<=100000)条双向边,第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N),该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N),它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B,但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物,然后再送给奶牛B。你的任务是:奶牛A至少需要走多远的路程?
输入输出格式
输入格式:
Line 1: Three space separated integers: N, M, and B
- Lines 2..M+1: Line i+1 describes cowpath i with three
space-separated integers: R_i, S_i, and L_i
- Lines M+2..M+B+1: Line M+i+1 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
输入输出样例
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
6
6
10 水题磨时间、、
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue> using namespace std; const int N(+);
const int M(+);
int n,m,b; int head[N],sumedge;
struct Edge
{
int v,next,w;
Edge(int v=,int next=,int w=):
v(v),next(next),w(w){}
}edge[M<<];
void ins(int u,int v,int w)
{
edge[++sumedge]=Edge(v,head[u],w);
head[u]=sumedge;
} queue<int>que;
bool inq[N];
int dis[N];
void SPFA()
{
memset(dis,/,sizeof(dis));
inq[]=; que.push(); dis[]=;
for(int u,v;!que.empty();)
{
u=que.front(); que.pop(); inq[u]=;
for(int i=head[u];i;i=edge[i].next)
{
v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!inq[v]) inq[v]=,que.push(v);
}
}
}
} int main()
{
scanf("%d%d%d",&n,&m,&b);
for(int u,v,w;m--;)
{
scanf("%d%d%d",&u,&v,&w);
ins(u,v,w); ins(v,u,w);
}
SPFA();
for(int u,v;b--;)
{
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]);
}
return ;
}
最新文章
- UML大战需求分析--阅读笔记01
- 与你相遇好幸运,Sail.js定义其他主键
- 内存和flash存储的区别
- 转centos65安装简测mysql cluster 7.3.7
- 树形DP 2013多校8(Terrorist’s destroy HDU4679)
- 【python cookbook】【数据结构与算法】10.从序列中移除重复项且保持元素间顺序不变
- 硬件描述语言Verilog设计经验总结
- UrlRewriteFilter 美化器的使用方法 伪静态化的解决方案(转)
- hbase 0.98.1集群安装
- 【转载】CSRF攻击及其应对之道
- android的Devices窗口中Online显示成Offline
- Python 包构建教程
- MongoDB的导入与导出
- ✔ OI Diary ★
- python装饰器扩展之functools.wraps
- 大数开方 ACM-ICPC 2018 焦作赛区网络预赛 J. Participate in E-sports
- linux环境java入门
- poj3281构图题
- Could not autowire. No beans of &#39;TbItemMapper&#39; type found. less... (Ctrl+F1) Checks autowiring prob
- SpringBoot 使用Thymeleaf解决静态页面跳转问题