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 此最相思 阅读(80) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理