题解 P3115 【[USACO15JAN]牛路线Cow Routing】

2018-07-28 09:48:28


这题没人用Dijkstra吗。。。

在原版Dijkstra的基础上把建图、堆节点的小于号重载、更新条件都改为双关键字的即可。

关键代码:

建图:

for (re int i=1;i<=k;i++) {
    int c=read(),n=read();
    for (re int j=1;j<=n;j++) { tmp[j]=read(); if (tmp[j]>nMAX) nMAX=tmp[j]; }
    for (re int p=1;p<n;p++)
        for (re int q=p+1;q<=n;q++)
            if ((c<G1[tmp[p]][tmp[q]]) || ((c==G1[tmp[p]][tmp[q]]) && (q-p<G2[tmp[p]][tmp[q]])))
                addEdge(tmp[p],tmp[q],c,q-p);
}

堆节点:

 struct Heapnode {
    int u,d,s;
    bool operator <(const Heapnode& rhs) const {
        return (d>rhs.d) || ((d==rhs.d) && (s>rhs.s));
    }
};

松弛:

if ((dis[u]+w1<dis[v])||((dis[u]+w1==dis[v])&&(st[u]+w2<st[v]))) {
    dis[v]=dis[u]+w1; st[v]=st[u]+w2;
    Q.push((Heapnode){v,dis[v],st[v]});
}

完整代码见蒟蒻的blog