Gym - 100570B ：ShortestPath Query（SPFA及其优化）

题意：给定N点M边的有向图，每条边有距离和颜色，一条有效路径上不能有相邻的边颜色相同。现在给定起点S，多次讯问S到点X的最短有效距离。

TLE思路：用二维状态dis(u,c)表示起点到u，最后一条边的颜色是c的最短距离，用map解决了二维空间不足的问题。但是T第151个点。所以需要优化，标解的优化是把dis(u,c)改为dis(u,0)或者dis(u,1)分别表示颜色同和不同的最短距离。

其他思路：用边表示通过那条边到点的最短距离。由于边自带颜色属性，所以就不需要其他状态了。这个方法比较直观，可以直接看代码。

TLE代码：（加了优化也不行。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

#define pii pair<int,int>

#define mp make_pair

#define Fi first

#define Se second

using namespace std;

const int maxn=;

const ll inf=1LL<<;

int Laxt[maxn],Next[maxn],To[maxn],W[maxn],C[maxn];

int S,N,cnt; ll ans[maxn];

deque<pii>q;

map<int,ll>dis[maxn];

map<int,int>vis[maxn];

void add(int u,int v,int w,int c){

    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v; W[cnt]=w; C[cnt]=c;

}

void spfa()

{

    rep(i,,N) ans[i]=inf; ans[S]=;

    for(int i=Laxt[S];i;i=Next[i]){

        dis[To[i]][C[i]]=W[i]; ans[To[i]]=W[i];

        vis[To[i]][C[i]]=;

        if(!q.empty()&&dis[To[i]][C[i]]<dis[q.front().Fi][q.front().Se])

        q.push_front(mp(To[i],C[i]));

        else q.push_back(mp(To[i],C[i]));

    }

    while(!q.empty()){

        pii H=q.front(); q.pop_front();

        int u=H.Fi,c=H.Se; ll tdis=dis[u][c]; vis[u][c]=;

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i];

            if(c==C[i]) continue;

            if(dis[v].find(C[i])==dis[v].end()){

                dis[v][C[i]]=tdis+W[i];

                ans[v]=min(ans[v],dis[v][C[i]]);

                if(!vis[v][C[i]]){

                     vis[v][C[i]]=;

                     if(!q.empty()&&dis[v][C[i]]<dis[q.front().Fi][q.front().Se]) q.push_front(mp(v,C[i]));

                     else q.push_back(mp(v,C[i]));

                }

            }

            else if(tdis+W[i]<dis[v][C[i]]){

                dis[v][C[i]]=tdis+W[i];

                ans[v]=min(ans[v],dis[v][C[i]]);

                if(!vis[v][C[i]]){

                     vis[v][C[i]]=;

                     if(!q.empty()&&dis[v][C[i]]<dis[q.front().Fi][q.front().Se]) q.push_front(mp(v,C[i]));

                     else q.push_back(mp(v,C[i]));

                }

            }

        }

    }

    rep(i,,N) if(ans[i]==inf) ans[i]=-;

}

int main()

{

    int M,CC,Q,u,v,w,c;

    scanf("%d%d%d",&N,&M,&CC);

    rep(i,,M){

        scanf("%d%d%d%d",&u,&v,&w,&c);

        add(u,v,w,c);

    }

    scanf("%d%d",&S,&Q);

    spfa();

    while(Q--){

        scanf("%d",&u);

        printf("%I64d\n",ans[u]);

    }

    return ;

}

AC代码：

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

using namespace std;

const int maxn=;

const ll inf=1LL<<;

int Laxt[maxn],Next[maxn],To[maxn],W[maxn],C[maxn];

int S,N,cnt,vis[maxn]; ll ans[maxn],dis[maxn];

void add(int u,int v,int w,int c){

    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v; W[cnt]=w; C[cnt]=c;

}

void spfa()

{

    deque<int>q;

    rep(i,,N) ans[i]=inf; ans[S]=;

    rep(i,,cnt) dis[i]=inf;

    for(int i=Laxt[S];i;i=Next[i]){

        dis[i]=W[i]; q.push_back(i); vis[i]=;

    }

    while(!q.empty()){

        int u=q.front();  q.pop_front(); vis[u]=;

        for(int i=Laxt[To[u]];i;i=Next[i]){

            if(C[u]!=C[i]){

                if(dis[i]>dis[u]+W[i]){

                    dis[i]=dis[u]+W[i];

                    if(!vis[i]) {

                        vis[i]=;

                        if(!q.empty()&&dis[i]<dis[q.front()]) q.push_front(i); //注意不要为空

                        else q.push_back(i);

                    }

                }

            }

        }

    }

    rep(i,,cnt) ans[To[i]]=min(ans[To[i]],dis[i]);

    rep(i,,N) if(ans[i]==inf) ans[i]=-;

}

int main()

{

    int M,CC,Q,u,v,w,c;

    scanf("%d%d%d",&N,&M,&CC);

    rep(i,,M){

        scanf("%d%d%d%d",&u,&v,&w,&c);

        add(u,v,w,c);

    }

    scanf("%d%d",&S,&Q);

    spfa();

    while(Q--){

        scanf("%d",&u);

        printf("%I64d\n",ans[u]);

    }

    return ;

}

巴特西

Gym - 100570B ：ShortestPath Query（SPFA及其优化）

最新文章

热门文章