ACM模板——次短路及K短路-白红宇

ACM模板——次短路及K短路

阅读量：5295 次

发布时间：2019-06-14

本文共 849 字，大约阅读时间需要 2 分钟。

#define P pair
      
       int d[maxn];int d2[maxn];int SSC(){    priority_queue
       
        ,greater
        > q;    memset(d,INF,sizeof(d));    memset(d2,INF,sizeof(d2));        d[0] = 0;    q.push(P(0,0));        while(!q.empty())    {        P p = q.top();q.pop();        int dis = p.first,v = p.second;        if(d2[v] < dis) continue;        _for(i,0,G[v].size())        {            edge &e = G[v][i];            int dis2 = dis + e.cost;            if(d[e.to] > dis2)            {                swap(d[e.to],dis2);                q.push(P(d[e.to],e.to));            }            if(d2[e.to] > dis2 && d[e.to] < dis2)            {                d2[e.to] = dis2;                q.push(P(d2[e.to],e.to));            }        }    }    return d2[V-1];}

次短路(如需还原路径参考最短路模板)

施工中

转载于:https://www.cnblogs.com/Asurudo/p/10592168.html

你可能感兴趣的文章