题目名称 133. [USACO Mar08] 牛跑步
输入输出 cowjog.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2008-09-29
开放分组 全部用户
提交状态
分类标签
通过:156, 提交:552, 通过率:28.26%
GravatarSky_miner 100 0.000 s C++
Gravatar槿柒 100 0.000 s C++
GravatarHzoi_chairman 100 0.000 s C++
GravatarLOSER 100 0.000 s C++
Gravatar可以的. 100 0.000 s C++
Gravatar面对疾风吧 疾风 疾风吧 100 0.000 s C++
Gravatar可以的. 100 0.000 s C++
GravatarSOBER GOOD BOY 100 0.000 s C++
Gravatar浮生随想 100 0.000 s C++
GravatarTroywar 100 0.000 s C++
关于 牛跑步 的讨论
数据中有陷阱!
注意存图方法。
Gravatarybh
2010-10-09 13:18 1楼
一开始写的Heap+djistra,然后好像是djistra写错了。。。
后面改成spfa了
还是一道Astar
GravatarHouJikan
2014-09-04 22:09 2楼
Gravatarforever
2015-08-21 15:17 3楼
好费劲的Astar
Gravatar哒哒哒哒哒!
2016-04-06 18:18 4楼
A——star!
GravatarSky_miner
2016-04-09 20:53 5楼
GravatarSOBER GOOD BOY
2016-06-14 09:16 6楼
GravatarAntiLeaf
2017-05-25 15:56 7楼
上课保证好好听..............
GravatarGo灬Fire
2016-06-14 14:49 8楼
第一道A* k短路啊...
感觉有千万头Bessie在我身上践踏...
Gravatar洛克索耶夫
2016-06-14 21:35 9楼
Gravatar面对疾风吧 疾风 疾风吧
2016-06-15 15:05 10楼
这道题专门考察Yen算法,说A*的都被打脸。
GravatarYGOI_真神名曰驴蛋蛋
2016-06-16 10:36 11楼
GravatarAntiLeaf
2017-05-25 15:57 12楼
拓扑就A了啊……Yen算法大材小用了吧
Gravataryveh
2016-08-25 16:17 13楼
Gravataryveh
2016-08-25 16:18 14楼
拓扑不就完了吗。每次保留最小的k个,复杂度O(mk*lgk)
Gravatartraceback
2016-10-31 15:34 15楼
这图..居然特么还不是连通图..
GravatarOstmbh
2017-01-15 07:39 16楼
ctrlC+v上一题,忘记已经改变变量名的尴尬=-=
GravatarTroywar
2017-03-26 21:04 17楼
换了三个A*板子都不对,最后发现spfa出队忘将inqueue清零。。。身败名裂系列。。。。
GravatarHZOI_蒟蒻一只
2017-04-09 21:05 18楼
GravatarWildRage
2017-04-09 21:04 19楼
明明输出答案是对的 非要W 求助
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define road 10000+10
#define node 1000+10
struct Edge
{
int x,y,z,next;
Edge(int x=0,int y=0,int z=0,int next=0):
x(x),y(y),z(z),next(next){}
}edge[road];
struct date
{
int x,g,h;
bool operator < (const date &a) const
{
return g+h>a.g+a.h;
}
};
int nl,m,k,x,y,z,sumedge,s,e,size;
int head[node],ans[100+10],dis[node],cnt[node];
bool vis[node];
int add(int x,int y,int z)
{
edge[++sumedge]=Edge(x,y,z,head[x]);
return head[x]=sumedge;
}
void spfa()
{
queue <int> q;
memset(dis,127/3,sizeof(dis));
dis[s]=0;vis[s]=1;q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
vis[now]=0;
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].y;
if(dis[to]>dis[now]+edge[i].z)
{
dis[to]=dis[now]+edge[i].z;
if(!vis[to])
{
vis[to]=1;
q.push(to);
}
}
}
}
}
void Astar()
{
priority_queue <date> qq;
qq.push((date){e,0,dis[e]});
while(!qq.empty())
{
date nn=qq.top();qq.pop();
++cnt[nn.x];
if(cnt[nn.x]>k)continue;
if(nn.x==s){
ans[++size]=nn.g;
}
if(cnt[s]==k){
return;
}
for(int i=head[nn.x];i;i=edge[i].next)
{
qq.push( (date){edge[i].y,nn.g+edge[i].z,dis[edge[i].y]});
}
}
return;
}
int main()
{
// freopen("cowjog.in ","r",stdin);
// freopen("cowjog.out","w",stdout);
scanf("%d%d%d",&nl,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(x<y)swap(x,y);
add(x,y,z);
}
s=1;e=nl;
spfa();
memset(ans,-1,sizeof(ans));
Astar();
for(int i=1;i<=k;i++)
printf("%d\n",ans[i]);
return 0;
}
Gravatar
2017-09-06 07:35 20楼
安利一下自己博克https://www.cnblogs.com/Hale522520/
GravatarHale
2019-01-31 14:41 21楼

133. [USACO Mar08] 牛跑步

★★★   输入文件:cowjog.in   输出文件:cowjog.out   简单对比
时间限制:1 s   内存限制:128 MB

$Bessie$准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘,然后走回牛棚.

$Bessie$也不想跑得太远,所以她想走最短的路经. 农场上一共有$M (1 <= M <= 10,000)$条路,每条路连接两个用$1..N(1 <= N <= 1000)$标号的地点. 更方便的是,如果$X>Y$,则地点$X$的高度大于地点$Y$的高度. 地点$N$是$Bessie$的牛棚;地点$1$是池塘.

很快, $Bessie$厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出$K (1 <= K <= 100)$条不同的路经.为了避免过度劳累,她想使这$K$条路径为最短的$K$条路径.

请帮助$Bessie$找出这$K$条最短路经的长度.你的程序需要读入农场的地图, 一些从$X_i$到$Y_i$的路径和它们的长度$(X_i, Y_i, D_i)$. 所有$(X_i, Y_i, D_i)$满足$(1 <= Y_i < X_i; Y_i < X_i <= N, 1 <= D_i <= 1,000,000).$

题目名称: cowjog

输入格式:

  • 第$1$行: 3个数: $N,M,K$
  • 第$2..M+1$行: 第 $i+1 $行包含3个数 $X_i, Y_i,D_i$, 表示一条下坡的路.

样例输入 (cowjog.in):

5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1

输出格式:

  • 第$1..K$行: 第$i$行包含第$i$最短路径的长度,或$-1$如果这样的路径不存在.如果多条路径有同样的长度,请注意将这些长度逐一列出.

样例输出 (cowjog.out):

1
2
2
3
6
7
-1

输出解释:

路径分别为$(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),(5-4-3-2-1)$