程序设计竞赛模板之最短路Dijkstra算法

struct edge
{
        int to,cost;
};
int V;
vector<edge> G[MAXV];
int d[MAXV];

void dijkstra(int s)
{
    priority_queue< pair<int,int> , vector< pair<int,int> > ,greater< pair<int,int> > > q;
    fill(d,d+V+1,INF);
    d[s]=0;
    q.push( pair<int,int>(0,s) );
    while(!q.empty())
    {
         pair<int,int> p=q.top();
         q.pop();
         int v=p.second;
         if(d[v]<p.first)
            continue;
         int len=G[v].size();
         for(int i=0;i<len;++i)
         {
             edge e=G[v][i];
             if(d[e.to] > d[v] + e.cost)
             {
                 d[e.to] = d[v] + e.cost;
                 q.push(pair<int,int>(d[e.to],e.to));
             }
         }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注