【题解】Paid Roads [SP3953] [Poj3411]

传送门：\(\text{Paid}\) \(\text{Roads}\) \(\text{[SP3953]}\) \(\text{[Poj3411]}\)

【题目描述】

给出一张 \(n\) 个点 \(m\) 条边的有向图。对于每条边 \((x,y)\)，如果之前经过 \(z\) 点，那么费用为 \(p\)，否则为 \(r\)。求 \(1\) 到 \(n\) 的最小费用。如果无法到达则输出 “ \(\text{impossible}\) ”。

【样例】

样例输入：

4 5

1 2 1 10 10

2 3 1 30 50

3 4 3 80 80

2 1 2 10 10

1 3 2 10 50

样例输出：

110

【数据范围】

\(100 \%:\) \(1 \leqslant n,m \leqslant 10,\) \(0 \leqslant p_i,r_i \leqslant 100\)

【分析】

由于边的费用涉及到了是否经过某个点，而且\(n\) 较小，因此可以考虑状压。

将每个点 \(i\) 分为 \(2^n-1\) 层，第 \(j\) 层表示当前在第 \(i\) 个点，状态为 \(j\)（二进制第 \(k\) 位为 \(1\) 就表示已经经过了点 \(k\)，\(0\) 表示还未经过）的状态，跑一遍 \(\text{dijkstra}\) 或者 \(\text{SPFA}\) 即可。

也可以开一个二维的 \(\text{dis}\) 数组，\(dis[i][j]\) 表示当前在点 \(i\)，状态为 \(j\) 的最短路，在最短路算法里面按照 \(j\) 分类更新 \(dis\)。

另外注意一下坑点：每个点可经过多次。

个人喜欢把所有的点全部建好，直接跑裸的最短路（就像写网络流那样）。

第二种写法代码就不放了。

【Code】

#include<algorithm>

#include<cstdio>

#include<queue>

#define LL long long

#define Re register int

using namespace std;

const int N=10300,M=2e4+3,inf=2e9;

int n,m,x,y,z,p,r,o,V,ans,dis[N],pan[N],head[N];

struct QWQ{int x,d;inline bool operator<(QWQ O)const{return d>O.d;}};

struct QAQ{int w,to,next;}a[M<<1];priority_queue<QWQ>Q;

inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}

inline void in(Re &x){

    Re f=0;x=0;char c=getchar();

    while(c<'0'||c>'9')f|=c=='-',c=getchar();

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

    x=f?-x:x;

}

inline void dijkstra(Re st){

    for(Re i=0;i<=n*V;++i)dis[i]=inf,pan[i]=0;//注意初始化时应扫描到n*V

    Q.push((QWQ){st,dis[st]=0});

    while(!Q.empty()){

        Re x=Q.top().x;Q.pop();

        if(pan[x])continue;

        pan[x]=1;

        for(Re i=head[x],to;i;i=a[i].next)

            if(dis[to=a[i].to]>dis[x]+a[i].w)

                Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});

    }

}

inline int Poi(Re i,Re j){return j+(i-1)*V;}//当前在点i状态为j

int main(){

    // freopen("123.txt","r",stdin);

    in(n),in(m),V=(1<<n)-1;

    while(m--){

        in(x),in(y),in(z),in(p),in(r);

        for(Re j=0;j<=V;++j)

            if(j&(1<<x-1))//如果j中包含了x，由于点可经过多次，所以不必判断y的情况

                if(j&(1<<z-1))add(Poi(x,j),Poi(y,j|(1<<y-1)),p);//已经经过了z

                else add(Poi(x,j),Poi(y,j|(1<<y-1)),r);//还没有经过z

    }

    dijkstra(Poi(1,1));ans=inf;//出发点为：只经过了1的状态，当前在点1

    for(Re j=0;j<=V;++j)ans=min(ans,dis[Poi(n,j)]);

    if(ans==inf)puts("impossible");

    else printf("%d\n",ans);

}

巴特西

【题解】Paid Roads [SP3953] [Poj3411]

【题解】Paid Roads [SP3953] [Poj3411]

【题目描述】

【分析】

【Code】

最新文章

热门文章