misschuer

常用链接

统计

积分与排名

百事通

最新评论

(转)最短路径模版(Dijkstra)

#include <iostream>
#include <queue>
using namespace std;

typedef struct
{
    long v;
    long next;
    long cost;
}Edge;

typedef struct
{
    long v;
    long cost;
}node;

bool operator <(const node &a,const node &b)
{
    return a.cost>b.cost;
}

const long MAXN=10000;

priority_queue<node> q;

long m,n;//点,边

long p[MAXN];
Edge e[MAXN];
bool vist[MAXN];

void init()
{
    memset(p,-1,sizeof(p));
    memset(vist,0,sizeof(vist));

    while (!q.empty())
    {
        q.pop();
    }
    long i;
    long eid=0;

    for (i=0;i<m;++i)
    {
        long from,to,cost;
        scanf("%ld %ld %ld",&from,&to,&cost);
        
        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;
        
        //以下为无向图使用

        swap(from,to);

        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;
    }
}

void print(long cost)
{
    //cost==-1 则无解
    printf("%ld\n",cost);
}

void Dijkstra()
{
    init();
    
    long cost=0;

    long Start,End;

    scanf("%ld %ld",&Start,&End);

    node t;

    t.cost=0;
    t.v=Start;

    q.push(t);

    while (!q.empty())
    {
        t=q.top();
        q.pop();

        if (t.v==End)
        {
            break;
        }

        if (vist[t.v])
        {
            continue;
        }

        vist[t.v]=true;

        long j;
        for (j=p[t.v];j!=-1;j=e[j].next)
        {
            if (!vist[e[j].v])
            {
                node temp;
                temp.v=e[j].v;
                temp.cost=e[j].cost+t.cost;
                q.push(temp);
            }
        }
    }

    if (t.v==End)
    {
        cost=t.cost;
    }
    else
    {
        cost=-1;
    }

    print(cost);

}


int main()
{
    while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        Dijkstra();
    }
    return 0;
}

posted on 2010-01-11 20:44 此最相思 阅读(144) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理