2018HDU多校1-1003-Triangle Partition(hdu 6298)-简单图论

题意：

给出一个无向图，每个边有一个标号，在标号相同的边上走不增加花费，每走到标号不同的边上时，花费+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;
}