[BZOJ2644][POJ3967]Ideal Path（分层图）

57 阅读 0 评论 38 点赞

我是靠谱客的博主魔幻玉米，最近开发中收集的这篇文章主要介绍[BZOJ2644][POJ3967]Ideal Path（分层图），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

我是超链接

题解：

首先先倒序bfs，求出所有可以到n的点的最短路，因为边权为1，可以构建一个分层图
然后正序bfs，对于每一层选出到达这一层的最小颜色，对于相等的颜色，我们把这些点都放进去进行下一轮

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
const int M=200005;
int tot,nxt[M*2],point[N],v[M*2],c[M*2],dis[N],color[N],num,n,s[N];bool vis[N];
struct hh{int x,c;hh(int X=0,int C=0){x=X;c=C;}}tmp[N];
void addline(int x,int y,int z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z;
}
int cmp(hh a,hh b){return a.c<b.c;}
int main()
{
    int m;scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        addline(x,y,z);
    }
    queue<int>q;
    memset(dis,0x7f,sizeof(dis));
    dis[n]=0;q.push(n);
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0; 
        for (int i=point[now];i;i=nxt[i])
          if (dis[v[i]]>dis[now]+1)
          {
            dis[v[i]]=dis[now]+1;
            if (!vis[v[i]]) q.push(v[i]),vis[v[i]]=1;
          }
    }
    int id=0;memset(vis,0,sizeof(vis));int top=0;s[++top]=1;
    while (s[top]!=n)
    {
        int num=0;++id;
        for (int j=1;j<=top;j++)
          for (int i=point[s[j]];i;i=nxt[i])
            if (dis[v[i]]+1==dis[s[j]]) tmp[++num]=hh(v[i],c[i]);
        sort(tmp+1,tmp+num+1,cmp);
        top=0; s[++top]=tmp[1].x; color[id]=tmp[1].c; vis[s[1]]=1;
        for (int i=2;i<=num;i++)
          if (tmp[i].c==tmp[i-1].c)
          {
            if (!vis[tmp[i].x]) vis[tmp[i].x]=1,s[++top]=tmp[i].x;
           } else break;

    }
    printf("%dn",dis[1]);
    for (int i=1;i<=dis[1];i++) printf("%d ",color[i]);
}