[USACO Mar08] 牛跑步 --k短路

[USACO Mar08] 牛跑步

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

很快,

请帮助

题目名称: cowjog

输入格式:

样例输入 (cowjog.in):

输出格式:

样例输出 (cowjog.out):

输出解释:

路径分别为

  1 //0.002s
  2 
  3 #include <queue>
  4 #include <cstdio>
  5 #include <ctype.h>
  6 #include <cstring>
  7 #include <algorithm>
  8  
  9 using namespace std;
 10  
 11 const int MAXM=10010;
 12 const int MAXN=1010;
 13  
 14 int n,m,k;
 15  
 16 int dis[MAXN];
 17  
 18 bool vis[MAXN];
 19  
 20 struct SKT {
 21     int v;
 22     int dist;
 23     bool operator < (const SKT&p) const {
 24         return dist+dis[v]>p.dist+dis[p.v];
 25     }
 26 };
 27 SKT s;
 28  
 29 struct edge {
 30     int to;
 31     int next;
 32     int val;
 33     edge() {}
 34     edge(int to,int val,int next):to(to),val(val),next(next){}
 35 };
 36 edge e[MAXM<<1],r[MAXM<<1];
 37  
 38 int head[MAXN],Head[MAXN],tot;
 39  
 40 inline void add(int x,int y,int v) {
 41     e[++tot]=edge(y,v,head[x]);
 42     r[tot]=edge(x,v,Head[y]);
 43     head[x]=Head[y]=tot;
 44 }
 45  
 46 inline void read(int&x) {
 47     int f=1;register char c=getchar();
 48     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
 49     for(;isdigit(c);x=x*10+c-48,c=getchar());
 50     x=x*f;
 51 }
 52  
 53 void SPFA() {
 54     queue<int> Q;
 55     for(int i=1;i<=n;++i) dis[i]=0x7fffffff;
 56     dis[1]=0;
 57     vis[1]=true;
 58     Q.push(1);
 59     while(!Q.empty()) {
 60         int now=Q.front();
 61         Q.pop();
 62         vis[now]=false;
 63         for(int i=Head[now];i!=-1;i=r[i].next) {
 64             int to=r[i].to;
 65             if(dis[to]>dis[now]+r[i].val) {
 66                 dis[to]=dis[now]+r[i].val;
 67                 if(!vis[to]) Q.push(to),vis[to]=true;
 68             }
 69         }
 70     }
 71     return;
 72 }
 73  
 74 void Astar() {
 75     int ans=0;
 76     priority_queue<SKT> Q;
 77     s.v=n,s.dist=0;
 78     Q.push(s);
 79     while(!Q.empty()) {
 80         SKT now=Q.top();
 81         Q.pop();
 82         if(now.v==1) {
 83             printf("%d
",now.dist);
 84             ++ans;
 85         }
 86         if(ans==k) return;
 87         for(int i=head[now.v];i!=-1;i=e[i].next) {
 88             int to=e[i].to;
 89             if(to<now.v) {
 90                 SKT FAKER=now;
 91                 FAKER.v=to;FAKER.dist=now.dist+e[i].val;
 92                 Q.push(FAKER);
 93             }
 94         }
 95     }
 96     while(ans<k) printf("-1
"),++ans;
 97     return;
 98 }
 99  
100 int hh() {
101     freopen("cowjog.in","r",stdin);
102     freopen("cowjog.out","w",stdout);
103     memset(Head,-1,sizeof Head);
104     memset(head,-1,sizeof head);
105     read(n);read(m);read(k);
106     for(int x,y,z;m--;) {
107         read(x);read(y);read(z);
108         if(x>y) add(x,y,z);
109     }
110     SPFA();
111     Astar();
112     return 0;
113 }
114  
115 int sb=hh();
116 int main() {;}

SPFA+A*

  1 #include <queue>
  2 #include <cstdio>
  3 #include <ctype.h>
  4 #include <cstring>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int MAXM=10010;
 10 const int MAXN=1010;
 11 
 12 int n,m,k;
 13 
 14 int dis[MAXN];
 15 
 16 bool vis[MAXN];
 17 
 18 struct SKT {
 19     int v,val,h;
 20     int dist;
 21     SKT() {}
 22     SKT(int v,int dist):v(v),dist(dist) {}
 23     SKT(int x,int y,int z) {
 24         v=x;val=y;h=z;
 25         dist=val+h;
 26     }
 27     bool operator < (const SKT&p) const {
 28         return dist>p.dist;
 29     }
 30 };
 31 SKT s;
 32 
 33 struct edge {
 34     int to;
 35     int next;
 36     int val;
 37     edge() {}
 38     edge(int to,int val,int next):to(to),val(val),next(next){}
 39 };
 40 edge e[MAXM<<1],r[MAXM<<1];
 41 
 42 int head[MAXN],Head[MAXN],tot;
 43 
 44 inline void add(int x,int y,int v) {
 45     e[++tot]=edge(y,v,head[x]);
 46     r[tot]=edge(x,v,Head[y]);
 47     head[x]=Head[y]=tot;
 48 }
 49 
 50 inline void read(int&x) {
 51     int f=1;register char c=getchar();
 52     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
 53     for(;isdigit(c);x=x*10+c-48,c=getchar());
 54     x=x*f;
 55 }
 56 
 57 void Dijs() {
 58     priority_queue<SKT> Q;
 59     for(int i=1;i<=n;++i) dis[i]=0x3f3f3f3f;
 60     Q.push(SKT(1,0));
 61     dis[1]=0;
 62     while(!Q.empty()) {
 63         SKT now=Q.top();
 64         Q.pop();
 65         for(int i=Head[now.v];i!=-1;i=r[i].next) {
 66             int to=r[i].to;
 67             if(dis[to]>dis[now.v]+r[i].val) {
 68                 dis[to]=dis[now.v]+r[i].val;
 69                 Q.push(SKT(to,dis[to]));
 70             }
 71         }
 72     }
 73     return;
 74 }
 75 
 76 void Astar() {
 77     int ans=0;
 78     priority_queue<SKT> Q;
 79     s.v=n,s.dist=0;
 80     Q.push(s);
 81     while(!Q.empty()) {
 82         SKT now=Q.top();
 83         Q.pop();
 84         if(now.v==1) {printf("%d
",now.dist);++ans;}
 85         if(ans==k) return;
 86         for(int i=head[now.v];i!=-1;i=e[i].next) 
 87           Q.push(SKT(e[i].to,now.val+e[i].val,dis[e[i].to]));
 88     }
 89     while(ans<k) printf("-1
"),++ans;
 90     return;
 91 }
 92 
 93 int hh() {
 94     freopen("cowjog.in","r",stdin);
 95     freopen("cowjog.out","w",stdout);
 96     memset(Head,-1,sizeof Head);
 97     memset(head,-1,sizeof head);
 98     read(n);read(m);read(k);
 99     for(int x,y,z;m--;) {
100         read(x);read(y);read(z);
101         add(x,y,z);
102     }
103     Dijs();
104     Astar();
105     return 0;
106 }
107 
108 int sb=hh();
109 int main() {;}

Dijs+A*

作者：乌鸦坐飞机
出处：http://www.cnblogs.com/whistle13326/
新的风暴已经出现怎么能够停止不前穿越时空竭尽全力我会来到你身边微笑面对危险梦想成真不会遥远鼓起勇气坚定向前奇迹一定会出现