2018HDU多校7-1001-Age of Moyu(hdu 6386)-最短路变形

题意：

给出一个无向图，每个边有一个标号，在标号相同的边上走不增加花费，每走到标号不同的边上时，花费+1，求从1~n的最小花费
（狗才摸鱼…）

思路：

与最短路问题极为相似，考虑对最短路算法进行修改
在spfa算法的基础上，遍历每个点，使用set记录由哪条边到达该点，若花费相同时，优先选由相同标号边到达的点，不同时按照正常spfa选择花费小的点，这样既可得到答案

其他方法：

bfs+dfs，从起点开始，进行bfs枚举花费，每次花费+1，然后dfs找出所有当前花费能到达的点，对每条边进行标记，每条边只访问一次，若到达n点即停止，当前花费就是到达n所需的最小花费

代码：

最短路修改法：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int MAX_N=1000005;
const int INF=0x3f3f3f3f;
struct node
{
    int next,to,cost;
}e[1000005];

struct nod
{
    int val;         //记录花费
    set<int>d;          //记录边的标号
}d[1000005];

int p[1000005],eid;
void init()
{
    eid=0;
    memset(p,-1,sizeof(p));
}

void insert(int u,int v,int w)
{
    e[eid].to=v;
    e[eid].cost=w;
    e[eid].next=p[u];
    p[u]=eid++;
}
int n,m;
bool inq[MAX_N];
int cnt[MAX_N];  //记录每个顶点入队次数，若某点入队超过n次，则存在负环
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    for(int i=0;i<=n;i++)
        d[i].val=INF,d[i].d.clear();
    d[s].val = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
        while(!q.empty())
    {
        int u=q.front();q.pop();inq[u]=0;
        for(int i=p[u];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            if(d[to].val>(d[u].val+(d[u].d.find(e[i].cost)==d[u].d.end())))          //若花费小于当前花费，修改并入队
            {
                d[to].val=d[u].val+(d[u].d.find(e[i].cost)==d[u].d.end());
                d[to].d.clear();d[to].d.insert(e[i].cost);
                if(!inq[to])
                {
                    q.push(to);inq[to]=1;
                }
            }
            else if(d[to].val==(d[u].val+(d[u].d.find(e[i].cost)==d[u].d.end()))&&d[to].d.find(e[i].cost)==d[to].d.end())         //若花费等于当前花费，优先选相同标号的边，并入队
            {
                d[to].d.insert(e[i].cost);
                if(!inq[to])
                {
                    q.push(to);inq[to]=1;
                }
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            insert(u,v,w);
            insert(v,u,w);
        }
        spfa(1);
        if(d[n].val==INF)
            cout<<-1<<endl;
        else
            cout<<d[n].val<<endl;
    }
    return 0;
}

dfs+bfs法：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=100005;
const int INF=0x3f3f3f3f;

int n,m;
struct node
{
    int next,to,cost;
}e[4*maxn];
int eid,p[maxn];
void init()
{
    eid=0;
    memset(p,-1,sizeof(p));
}
void insert(int u,int v,int c)
{
    e[eid].to=v;
    e[eid].cost=c;
    e[eid].next=p[u];
    p[u]=eid++;
}
void addedge(int u,int v,int c)
{
    insert(u,v,c);
    insert(v,u,c);
}
struct nod
{
    int from,nd,id;
};

bool vis[maxn],flag=0;
int ans=0;
queue<nod>Q;
void dfs(nod now)
{
    vis[now.id]=1;
    if(flag) return;
    if(now.id==n)
    {
        ans=now.nd;
        flag=1;
        return;
    }

    for(int i=p[now.id];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        int from=now.from;
        if(vis[to]) continue;
        if(e[i].cost==from || from==-1)
        {
            nod next;
            next.id=to;
            next.nd=now.nd;
            next.from=e[i].cost;
            dfs(next);
        }
        else
        {
            nod next;
            next.id=to;
            next.nd=now.nd+1;
            next.from=e[i].cost;
            Q.push(next);
        }
    }
}

void bfs(int s)
{
    memset(vis,0,sizeof(vis));
    while(!Q.empty()) Q.pop();
    flag=0;
    nod sta;
    sta.from=-1;
    sta.nd=1;
    sta.id=s;
    vis[s]=1;
    Q.push(sta);
    while(!Q.empty())
    {
        if(flag) return;
        nod now=Q.front();
        Q.pop();
        dfs(now);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            int u,v,c;
            cin>>u>>v>>c;
            addedge(u,v,c);
        }
        bfs(1);
        if(flag)
            cout<<ans<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}