problem.php?pid=133

★★★ 输入文件：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<queue>

#include<cstdio>

#include<cstring>

#define N 1001

#define M 10001

using namespace std;

int n,s,t,k;

int dis1[N];

bool vis[N];

int front[N],to[M],nxt[M],val[M],tot;

int front2[N],to2[M],nxt2[M],val2[M],tot2;

struct node

{

    int num,dis;

    bool operator < (node p) const

    {

        return dis+dis1[num]>p.dis+dis1[p.num];

    }

}now,nt;

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

    to2[++tot2]=u; nxt2[tot2]=front2[v]; front2[v]=tot2; val2[tot2]=w;

}

void init()

{

    int m,u,v,w;

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

    while(m--)

    {

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

}

void spfa()

{

    memset(dis1,,sizeof(dis1));

    queue<int>q;

    dis1[]=;

    vis[]=true;

    q.push();

    int now;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        vis[now]=false;

        for(int i=front2[now];i;i=nxt2[i])

            if(dis1[to2[i]]>dis1[now]+val2[i])

            {

                dis1[to2[i]]=dis1[now]+val2[i];

                if(!vis[to2[i]])

                {

                    q.push(to2[i]);

                    vis[to2[i]]=true;

                }

            }

    }

}

void Astar()

{

    if(dis1[n]>1e9)

    {

        for(int i=;i<=k;i++) printf("-1\n");

        return;

    }

    int cnt=;

    priority_queue<node>q;

    now.num=n;

    now.dis=;

    q.push(now);

    while(!q.empty())

    {

        now=q.top();

        q.pop();

        if(now.num==)

        {

            cnt++;

            printf("%d\n",now.dis);

            if(cnt==k) return;

        }

        for(int i=front[now.num];i;i=nxt[i])

        {

            nt.num=to[i];

            nt.dis=now.dis+val[i];

            q.push(nt);

        }

    }

    for(int i=cnt+;i<=k;i++) printf("-1\n");

}

int main()

{

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

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

    init();

    spfa();

    Astar();

}

巴特西

[USACO Mar08] 牛跑步

http://www.cogs.pro/cogs/problem/problem.php?pid=133

最新文章

热门文章