COGS 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):

输出格式:

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

样例输出 (cowjog.out):

输出解释:

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

k短路模板

屠龙宝刀点击就送

#include <cstdio>

#include <queue>

#define N 10500

#define INF 0x7fffffff

using namespace std;

struct Edge

{

    int next,to,dis;

};

Edge edge1[N],edge2[N];

bool vis[N];

int n,m,k,head1[N],head2[N],cnt,dis[N];

inline void ins(int u,int v,int w)

{

    edge1[++cnt]=(Edge){head1[u],v,w};

    head1[u]=cnt;

    edge2[cnt]=(Edge){head2[v],u,w};

    head2[v]=cnt;

}

void spfa(int s)

{

    for(int i=;i<=n;++i) dis[i]=INF;

    dis[s]=;

    queue<int>q;

    q.push(s);

    for(int now;!q.empty();)

    {

        now=q.front();q.pop();

        vis[now]=;

        for(int i=head2[now];i;i=edge2[i].next)

        {

            int v=edge2[i].to;

            if(dis[v]>dis[now]+edge2[i].dis)

            {

                dis[v]=dis[now]+edge2[i].dis;

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

}

struct node

{

    int to,f,g;

    bool operator<(node a)const

    {

        if(f==a.f) return g>a.g;

        else return f>a.f;

    }

};

void Astar()

{

    int cnt=;

    priority_queue<node>q;

    node a;

    a.to=n;

    a.g=;

    a.f=a.g+dis[a.to];

    q.push(a);

    for(node now;!q.empty();)

    {

        now=q.top();q.pop();

        if(now.to==) {cnt++;printf("%d\n",now.g);}

        if(cnt==k) return;

        for(int i=head1[now.to];i;i=edge1[i].next)

        {

            int v=edge1[i].to;

            node tmp;

            tmp.to=v;

            tmp.g=now.g+edge1[i].dis;

            tmp.f=tmp.g+dis[tmp.to];

            q.push(tmp);

        }

    }

    for(;cnt<k;) printf("-1\n"),cnt++;

}

int Main()

{

    freopen("cowjog.in","r",stdin);

    freopen("cowjog.out","w",stdout);

    scanf("%d%d%d",&n,&m,&k);

    for(int x,y,z,i=;i<=m;++i)

    {

        scanf("%d%d%d",&x,&y,&z);

        if(x>y) ins(x,y,z);

    }

    spfa();

    Astar();

    return ;

}

int sb=Main();

int main() {;}

巴特西

COGS 133. [USACO Mar08] 牛跑步

最新文章

热门文章