Snuke's Subway Trip

すぬけ君の地下鉄旅行 / Snuke's Subway Trip

Time limit : 3sec / Memory limit : 256MB

Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1≤i≤M ) line connects station pi and qi bidirectionally. There is no intermediate station. This line is operated by company ci.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2≤N≤105
0≤M≤2×105
1≤pi≤N (1≤i≤M)
1≤qi≤N (1≤i≤M)
1≤ci≤106 (1≤i≤M)
pi≠qi (1≤i≤M)

Input

The input is given from Standard Input in the following format:

N M
p1 q1 c1

:
pM qM cM

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

Sample Output 1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

分析：根据贪心思想，从一个点到另一个点必然是从之前点最小花费转移过来的，否则不会更优；

　　　所以每个点维护最小花费和到达前的公司id，用最短路拓展即可；

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define Lson L, mid, rt<<1

#define Rson mid+1, R, rt<<1|1

const int maxn=1e5+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

int n,m,k,t,h[maxn],tot,ans[maxn];

set<int>comp[maxn];

struct node

{

    int to,nxt,com;

}e[maxn<<];

void add(int x,int y,int z)

{

    tot++;

    e[tot].to=y;

    e[tot].com=z;

    e[tot].nxt=h[x];

    h[x]=tot;

}

priority_queue<pair<int,int> >p;

int main()

{

    int i,j;

    memset(ans,inf,sizeof ans);

    scanf("%d%d",&n,&m);

    while(m--)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

        add(b,a,c);

    }

    p.push({,});ans[]=;

    while(!p.empty())

    {

        int now=p.top().se,ca=-p.top().fi;

        p.pop();

        if(ans[now]<ca)continue;

        for(i=h[now];i;i=e[i].nxt)

        {

            int to=e[i].to,to_com=e[i].com;

            int to_ca=ca+(!comp[now].count(to_com));

            if(ans[to]>to_ca)

            {

                ans[to]=to_ca;

                p.push({-to_ca,to});

                comp[to].clear();

                comp[to].insert(to_com);

            }

            else if(ans[to]==to_ca)

            {

                comp[to].insert(to_com);

            }

        }

    }

    printf("%d\n",ans[n]==inf?-:ans[n]);

    //system("Pause");

    return ;

}

秒客网