HDU 6386 Age of Moyu 【bfs】【spfa】

Age of Moyu

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2585    Accepted Submission(s): 784

 

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 −1instead)

 

 

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

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e6 + 7;
const int INF = 0x3f3f3f3f;

int dis[MAX], vis[MAX];
int n, m;

struct node{
    int id, col;
    node() {}
    node(int id, int col) : id(id), col(col) {}
};

struct edge{
    int to, c;
    edge() {}
    edge(int to, int c) : to(to), c(c) {}
};

vector <edge> v[MAX];

void add(int x, int y, int z){
    v[x].push_back(edge(y, z));
}

void spfa(){
    memset(vis, 0, sizeof vis);
    memset(dis, INF, sizeof dis);
    vis[1] = 1, dis[1] = 0;
    queue <node> q;
    q.push(node(1, 0));
    while(!q.empty()){
        node u = q.front();
        vis[u.id] = 0;
        q.pop();
        for(int i = 0; i < v[u.id].size(); i++){
            int to = v[u.id][i].to;
            int c = v[u.id][i].c;
            if(c == u.col){
                if(dis[to] > dis[u.id]){
                    dis[to] = dis[u.id];
                    if(!vis[to]){
                        vis[to] = 1;
                        q.push(node(to, c));
                    }
                }
            }
        }
        for(int i = 0; i < v[u.id].size(); i++){
            int to = v[u.id][i].to;
            int c = v[u.id][i].c;
            if(dis[to] > dis[u.id] + 1){
                dis[to] = dis[u.id] + 1;
                if(!vis[to]){
                    vis[to] = 1;
                    q.push(node(to, c));
                }
            }
        }
    }
    if(dis[n] == INF) puts("-1");
    else printf("%d\n", dis[n]);
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        for(int i = 0; i <= n; i++) v[i].clear();
        for(int i = 0, x, y, z; i < m; i++){
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z), add(y, x, z);
        }
        spfa();
    }
    return 0;
}