洛谷3115 牛路线Cow Routing

Luogu

算法

显然是最短路。但这个题目有两个条件,所以是双关键字的最短路。

那么在单关键字的Dijkstra/SPFA上改一改。比如把Dijkstra的堆优化的<重载改掉、把松弛的条件改掉。

当然建图也是要改的。注意这道题只能用邻接矩阵。
(我用邻接表要么RE要么MLE)

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int G1[1010][1010];
int G2[1010][1010];

inline int addEdge(int u,int v,int w1,int w2) {
//    printf("%lld %lld %lld %lld\n",u,v,w1,w2);
    G1[u][v]=w1;
    G2[u][v]=w2;
}

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

int nMAX=-1,k,s,t;
int dis[2010];
int st[2010];
priority_queue<Heapnode> Q;

inline void Dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    memset(st,0x3f,sizeof(st));
    dis[s]=st[s]=0; Q.push((Heapnode){s,0,0});
    while (!Q.empty()) {
        Heapnode fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d,step=fr.s;
        if (dis[u]!=d||st[u]!=step) continue;
        for (re int v=1;v<=nMAX;v++) {
            int w1=G1[u][v],w2=G2[u][v];
            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]});
            }
        }
    }
}

int tmp[110];

mainint main() {
    memset(G1,0x3f,sizeof(G1));
    memset(G2,0x3f,sizeof(G2));
    s=read(),t=read(),k=read();
    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);
    }
    Dijkstra();
    if (dis[t]==dis[0]) printf("-1 -1\n");
    else printf("%lld %lld\n",dis[t],st[t]);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 03 PM

发表评论