无法拯救我的菜系列------hdu6386 Age of Moyu

Age of Moyu
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2384 Accepted Submission(s): 714

Problem Description
Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting of N ports and M shipping lines. The ports are numbered 1 to N. Each line is occupied by a Weitian. Each Weitian has an identification number.

The i-th (1≤i≤M) line connects port Ai and Bi (Ai≠Bi) bidirectionally, and occupied by Ci Weitian (At most one line between two ports).

When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 1 XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of 1 XiangXiangJi. In a case where Mr.Quin changed from some Weitian A’s line to another Weitian’s line changes to Weitian A’s line again, the additional cost is incurred again.

Mr.Quin is now at port 1 and wants to travel to port N where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port N, print −1 instead)

Input
There might be multiple test cases, no more than 20. You need to read till the end of input.

For each test case,In the first line, two integers N (2≤N≤100000) and M (0≤M≤200000), representing the number of ports and shipping lines in the city.

In the following m lines, each contain three integers, the first and second representing two ends Ai and Bi of a shipping line (1≤Ai,Bi≤N) and the third representing the identification number Ci (1≤Ci≤1000000) of Weitian who occupies this shipping line.

Output
For each test case output the minimum required cost. If Mr.Quin can’t travel to port N, output −1 instead.

Sample Input
3 3
1 2 1
1 3 2
2 3 1
2 0
3 2
1 2 1
2 3 2

Sample Output
1
-1
2

赛场上居然会用爆搜路径，真的脑子坏掉了，求最短，一般用宽搜
这道题的做法很多，我觉得这种做法歧义性小一点
思路： bfs查询路径，每条路都只走一次，每个点只询问一次。每一个点入队列后，再用dfs把所有与当前路径相同权值的路径加入。本质上是记录依次花费1,2，….步能到达哪里。bfs先查到的一定是从1到n的最短路径。
转载：https://blog.csdn.net/jinghui_7/article/details/81637788

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 5;
#define pb push_back

typedef struct Node{
    int to,vis,w;
}Node;

bool vis[N];
vector<Node>ve[N];
int dis[N];
int res;
int n,m;
queue<int>que;

void dfs(int id,int pre,int num)
{
    if(id == n){
        res = num;
        return ;
    }
    if(!vis[id]){
        dis[id] = num;
        vis[id] = true;
        que.push(id);
    }
    for(int i = 0;i < ve[id].size();++i)
    {
        if(ve[id][i].vis == 1)
            continue;
        if(ve[id][i].w == pre){
            ve[id][i].vis = 1;
            dfs(ve[id][i].to,pre,num);
        }
    }
}
//枚举换乘次数1，2，.....
//每个点只扫描一次，每条边只扫描一次
int bfs()
{
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    while(!que.empty())
        que.pop();
    vis[1] = true;
    dis[1] = 0;
    que.push(1);
    while(!que.empty())
    {
        int tmp = que.front();
        que.pop();
        for(int i = 0;i < ve[tmp].size();++i)
        {
            if(ve[tmp][i].vis == 1)
                continue;
            ve[tmp][i].vis = 1;
            dfs(ve[tmp][i].to,ve[tmp][i].w,dis[tmp] + 1);
            if(res > 0){
                break;
            }
        }
        if(res > 0){
            break;
        }
    }
    return res;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 1;i <= n;++i)
            ve[i].clear();
        for(int i = 0;i < m;++i)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            ve[a].pb((Node){b,0,c});
            ve[b].pb((Node){a,0,c});
        }
        res = -1;
        res = bfs();
        printf("%d\n",res);
    }
    return 0;
}

网上还有spfa版求最短路（感觉是玄学AC，我必须把权值相等可更新的点先全部入队列，不然就会WA）：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 5;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

vector< pair<int,int> >ve[N];
typedef struct Node{
    int id;//存储被更新的点
    int company;//存储该点前一条边的公司编号
}Node;
int dis[N];
bool vis[N];

void spfa()
{
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    queue<Node>que;
    vis[1] = true;
    dis[1] = 0;
    que.push((Node){1,0});
    while(!que.empty())
    {
        Node tmp = que.front();
        que.pop();
        vis[tmp.id] = false;
        //必须把权值相等的全部处理完再处理不相同的，因为这与下次取出的次序有关
        //把相同权值的点先放进去，下次一定先取出来
        for(int i = 0;i < ve[tmp.id].size();++i)
        {
            int now = ve[tmp.id][i].se;
            int nxt = ve[tmp.id][i].fi;
            if(now == tmp.company){
                if(dis[tmp.id] < dis[nxt]){
                    dis[nxt] = dis[tmp.id];
                    if(!vis[nxt]){
                        vis[nxt] = true;
                        que.push((Node){nxt,now});
                    }
                }
            }
        }
        for(int i = 0;i < ve[tmp.id].size();++i)
        {
            int now = ve[tmp.id][i].se;
            int nxt = ve[tmp.id][i].fi;
            if(now != tmp.company){
                if(dis[tmp.id] + 1 < dis[nxt]){
                    dis[nxt] = dis[tmp.id] + 1;
                    if(!vis[nxt]){
                        vis[nxt] = true;
                        que.push((Node){nxt,now});
                    }
                }
            }
        }
    }
}

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 1;i <= n;++i)
        {
            ve[i].clear();
        }
        for(int i = 0;i < m;++i)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            ve[a].pb(mp(b,c));
            ve[b].pb(mp(a,c));
        }
        spfa();
        if(dis[n] >= inf){
            printf("-1\n");
        }
        else{
            printf("%d\n",dis[n]);
        }
    }
    return 0;
}

还有一个用优先队列宽搜的版本，每次将最小花费的点提前取出去更新其他点，每个点都只更新一次（我也感觉是玄学AC，改一下结构体的运算符重载函数，只有一种情况会A,就是当最小花费相同时，将id较大的点往前放）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 100005;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

vector<pair<int,int> >ve[N];
bool vis[N];

typedef struct Node{
    int val;//存当前的最小花费
    int id;//当前节点
    int company;//存当前节点的前一条线的公司编号
    friend bool operator < (const Node &p,const Node &q)
    {
        if(q.val == p.val){
            return p.id < q.id;
        }
        else{
            return p.val > q.val;
        }
    }
}Node;

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        memset(vis,false,sizeof(vis));
        for(int i = 1;i <= n;++i)
            ve[i].clear();
        for(int i = 0; i < m;++i)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            ve[a].pb(mp(b,c));
            ve[b].pb(mp(a,c));
        }
        //用优先队列是因为每次找出来的是最小花费，用最小花费去更新其他点
        priority_queue<Node>que;
        Node tmp,res;
        tmp.company = -1;
        tmp.id = 1;
        tmp.val = 0;
        que.push(tmp);

        int ans = -1;
        while(!que.empty())
        {
            tmp = que.top();
            que.pop();
            if(tmp.id == n){
               ans = tmp.val;
               break;
            }
            vis[tmp.id] = true;
            int len = ve[tmp.id].size();
            for(int i = 0;i < len;++i)
            {
                int nxt = ve[tmp.id][i].fi;
                int com = ve[tmp.id][i].se;
                if(vis[nxt])
                    continue;
                if(com == tmp.company){
                    res.company = com;
                    res.id = nxt;
                    res.val = tmp.val;
                    que.push(res);
                }
                else{
                    res.company = com;
                    res.id = nxt;
                    res.val = tmp.val + 1;
                    que.push(res);
                }
            }
        }
        cout << ans << endl;

    }
    return 0;
}