cogs 133. [USACO Mar08] 牛跑步

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条最短路经的长度.你的程序需要读入农场的地图, 一些从Xi到Yi的路径和它们的长度(Xi,Yi,Di). 所有(Xi,Yi,Di)满足(1<=Yi<Xi;Yi<Xi<=N,1<=Di<=1,000,000).

题目名称: cowjog

输入格式:

• 第1行: 3个数: N,M,K

• 第2..M+1行: 第 i+1行包含3个数 Xi,Yi,Di, 表示一条下坡的路.

样例输入 (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)

 

思路：k短路版子。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXN 600000
#include<queue>
using namespace std;
struct nond{
    int g,f,to;
    bool operator<(const nond &r) const {
        if(r.f==f)    return r.g<g;
        else return r.f<f;
    }
}tmp,opt;
int n,m,k,s,t,cnt,tot,tot1;
int dis[MAXN],vis[MAXN];
int to[MAXN],head[MAXN],net[MAXN],cap[MAXN];
int to1[MAXN],head1[MAXN],net1[MAXN],cap1[MAXN];
void add(int u,int v,int w){
    to[++tot]=v;net[tot]=head[u];cap[tot]=w;head[u]=tot;
    to1[++tot1]=u;net1[tot1]=head1[v];cap1[tot1]=w;head1[v]=tot1;
}
void spfa(int s){
    queue<int>que1;
    for(int i=0;i<=n;i++)    dis[i]=INF;
    que1.push(s);
    vis[s]=1;dis[s]=0;
    while(!que1.empty()){
        int now=que1.front();
        que1.pop();
        vis[now]=0;
        for(int i=head1[now];i;i=net1[i])
            if(dis[to1[i]]>dis[now]+cap1[i]){
                dis[to1[i]]=dis[now]+cap1[i];
                if(!vis[to1[i]]){
                    vis[to1[i]]=1;
                    que1.push(to1[i]);
                }
            }
    }
}
int Astar(int kk){
    priority_queue<nond>que;
    if(s==t)    kk++;
    if(dis[s]==INF)    return -1;
    tmp.g=0;
    tmp.to=s;
    tmp.f=dis[s];
    que.push(tmp);
    while(!que.empty()){
        tmp=que.top();
        que.pop();
        if(tmp.to==t)    cnt++;
        if(cnt==kk)    return tmp.g;
        for(int i=head[tmp.to];i;i=net[i]){
            opt.to=to[i];
            opt.g=tmp.g+cap[i];
            opt.f=opt.g+dis[to[i]];
            que.push(opt);
        }
    }
    return -1;
}
int main(){
    freopen("cowjog.in","r",stdin);
    freopen("cowjog.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    s=n;t=1;
    spfa(s);
    for(int i=1;i<=k;i++){
        cnt=0;
        printf("%d
",Astar(i));
    }
}