Age of Moyu(bfs)

2018-08-15

Age of Moyu

题意

给你n个点，m条边，要求从1号走到n号，每条边上都有一种颜色，如果你在相同颜色的边上走，不会有额外的花费，但是如果你从一种颜色的边走到另一种颜色的边上，那么就要加1的花费，求的是最小花费。

1<=n<=1e5, 0<=m<=2e5

多组。

思路

如果直接bfs优先队列处理大顶堆的话，把跑过的点或者边标记了的话，是考虑不周到的。

如：

6 8

1 2 2

2 3 2

3 4 2

1 4 1

1 5 1

4 5 2

5 6 2

2 6 1 答案应该是1，但是很多都容易输出2。

正确的做法是，用set[i]储存每次到达点i的前驱结点，如果到达这个点的花费比历史中到达这个点的最小花费要大，就continue,如果相等，前驱结点在set中，continue，如果不在set中，就放入set中，如果小于的话，就把set[i]清空，然后把历史最小花费mincost[i]更新了，并且把前驱结点放到set中（我发现放这条边的颜色也是可以的），然后对当前这个点连出去的每一条边继续判断，如果不是反向边，而且mincost[nxt]>=（(当前颜色!=下个颜色)+mincost[i]），就把mincost[nxt]更新了，并且如果nxt点不是终点，就把nxt点push到优先队列中，优先队列存的是每一个点的到达状态，按照到达的花费从小到大放。

看！代码

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn =1e5+5;
struct edge{
    int to,color,nxt; //下一个点，这条边的颜色，对于这个点相连的下一条边
}e[maxn<<2];
set<int>preid[maxn]; //到达某点时花费相同的前一个结点
int idcost[maxn]; //到达某点的最小花费
int head[maxn]; //暂时记录上一条边的

struct node{
    int val,id;//当前总花费，当前到达点
    int color,father;//前一条边上的颜色，前一个结点
    bool operator <(const node &p) const{return val>p.val;}
};

int solve(int n)
{
    priority_queue<node>q;
    idcost[1]=0;
    q.push((node){idcost[1],1,-1,-1});
    int len,id,color,father,tot,i,cl,nxt;
    node tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        id=tmp.id,tot=tmp.val,father=tmp.father,color=tmp.color;
        if(tot>idcost[id]) continue; //如果当前到达的总花费比到这一点的最小的花费要贵
        else if(tot==idcost[id])
        {
            if(preid[id].find(color)!=preid[id].end()) //如果当前到达点已经记录了前一个点的颜色//我发现father前驱结点也是对的
                continue;
            preid[id].insert(color);
        }
        else //更新最小花费
        {
            preid[id].clear();
            preid[id].insert(color);
            idcost[id]=tot;
        }
        for(i=head[id];~i;i=e[i].nxt) //对于这个点连接的其他点
        {
            cl=e[i].color;
            nxt=e[i].to;
            if(nxt==father) continue; //反向边
            if(((cl!=color)+idcost[id])<=idcost[nxt])
            {
                idcost[nxt]=(cl!=color)+idcost[id];
                if(nxt!=n)
                    q.push((node){idcost[nxt],nxt,cl,id});
            }
        }
    }
    if(idcost[n]==INF) return -1;
    return idcost[n];
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int n,m;
    int u,v,w;
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        memset(idcost,INF,sizeof(idcost));
        int total=0;
        for(int i=1;i<=n;i++)
            preid[i].clear();
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            e[total]=(edge){v,w,head[u]}; //一种新型存边方式hhh
            head[u]=total++;
            e[total]=(edge){u,w,head[v]};
            head[v]=total++;
        }
        printf("%d\n",solve(n));
    }
    return 0;
}