首页 > 代码库 > 186. [USACO Oct08] 牧场旅行
186. [USACO Oct08] 牧场旅行
186. [USACO Oct08] 牧场旅行(点击转到COGS)
输入文件:pwalk.in 输出文件:pwalk.out
时间限制:1 s 内存限制:128 MB
描述
n个被自然地编号为1..n奶牛(1<=n<=1000)正在同样被方便的编号为1..n的n个牧场中吃草。更加自然而方便的是,第i个奶牛就在第i个牧场中吃草。
其中的一些对牧场被总共的n-1条双向通道的一条连接。奶牛可以通过通道。第i条通道连接的两个牧场是A_i和B_i(1<=A_i<=N;1<=B_i<=N)其长度是L_i(1<=L_i<=10000)。
通道只会连接两个不同的牧场,所以这些通道使得整个牧场构成了一棵树。
奶牛们是好交际的希望能够经常的访问别的奶牛。急切地,它们希望你能通过告诉它们Q(1<=Q<=1000)对牧场的路径来帮助他们安排旅行。(这里将有Q个询问,p1,p2(1<=p1<=n;1<=p1<=n))
分数:200
问题名称:pwalk
输入格式:
? 第1行:两个用空格隔开的整数:n和Q
? 第2..n行:第i+1行包含三个用空格隔开的整数:A_i,B_i和L_i
? 第n+1..N+Q行:每行包含两个用空格隔开的整数,代表两个不同的牧场,p1和p2
输入样例(file pwalk.in):
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
输出格式:
? 第1..Q行:行i包含第i个询问的答案。
输出样例:
2
7
输出说明:
询问1:牧场1和牧场2的路径长度为2。 询问2:3->4->1->2;总长为7。
思路:
最短路径(用的spfa,反正我的floyd会超时)
#include<cstdio> #include<cstring> #define N 1010 using namespace std; int n,q,p1,p2,ai,bi; int dis[N],map[N][N]; bool vis[N]; void spfa(int x) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); int que[N],q,head=0,tail=1; que[head]=x; vis[x]=1; dis[x]=0; while(head<tail) { q=que[head++]; vis[q]=0; for(int i=1;i<=n;i++) if(dis[i]>dis[q]+map[q][i]) { dis[i]=dis[q]+map[q][i]; if(!vis[i]) { que[tail++]=i; vis[i]=1; } } } } int main() { freopen("pwalk.in","r",stdin); freopen("pwalk.out","w",stdout); scanf("%d%d",&n,&q); int distance; memset(map,0x7f,sizeof(map));//用两层循环超时== 还是用memset for(int i=1;i<n;i++) { scanf("%d%d%d",&ai,&bi,&distance); map[ai][bi]=map[bi][ai]=distance; } for(int i=1;i<=q;i++) { scanf("%d%d",&p1,&p2); spfa(p1); printf("%d\n",dis[p2]); } fclose(stdin);fclose(stdout); return 0; }
186. [USACO Oct08] 牧场旅行
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。