Problem Description

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.

Example

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

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

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2
First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1

題意：n 個(gè)點(diǎn) m 條邊，每條邊給出鄰接點(diǎn)的同時(shí)給出一個(gè)價(jià)值，代表的是該邊所屬的公司，現(xiàn)在要從 1 號(hào)點(diǎn)到 n 號(hào)點(diǎn)，已知在同一個(gè)公司上行走時(shí)，無需付出任何代價(jià)，但當(dāng)走到令一公司的邊上時(shí)，需要花費(fèi) 1 元，求最小花費(fèi)

思路：

這個(gè)題的問題在于讓相同公司的道路之間行走花費(fèi)為 0，不同公司之間的道路行走花費(fèi)為 1，于是整張圖的每個(gè)公司可以看做一個(gè)虛點(diǎn)，其連接著其所屬的邊的兩點(diǎn)

由于在同一個(gè)公司的路上行走時(shí)，不耗費(fèi)任何價(jià)值，那么可以對(duì)同一公司的路上進(jìn)行拆點(diǎn)建圖，即對(duì)于所屬公司為 val 的邊 x-y，將其拆成 x-newX、newX-newY、newY-y 三條邊，其價(jià)值分別為 1、0、1，然后對(duì)整個(gè)圖跑 SPFA 求最短路即可

跑完 SPFA 時(shí)，由于在起點(diǎn)時(shí)需要一個(gè)初始代價(jià)，中間行走時(shí)不需要代價(jià)，離開時(shí)也需要一個(gè)代價(jià)，因此 dis[n]/2 就是答案

此外，重點(diǎn)在于如何拆點(diǎn)能保證點(diǎn)不重復(fù)，考慮到 map 的特性，我們令 mp[a][b] 的值從 n 號(hào)點(diǎn)開始遞增，從而保證點(diǎn)的唯一性

需要注意的是，由于拆完點(diǎn)后點(diǎn)和邊的數(shù)目會(huì)很多，因此數(shù)組范圍要開的大一點(diǎn)

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std; struct Edge {int to,next,val;Edge(){}Edge(int to,int next,int val):to(to),next(next),val(val){}bool operator < (const Edge& rhs)const{return val>rhs.val;} }edge[N*2]; int tot,head[N]; void addEdge(int from,int to,int val) {edge[tot].next=head[from];edge[tot].to=to;edge[tot].val=val;head[from]=tot++; } bool vis[N]; int dis[N]; int SPFA(int s,int e) {memset(vis,false,sizeof(vis));memset(dis,INF,sizeof(dis));dis[s]=0;priority_queue<Edge> Q;Q.push(Edge(s,0,0));while (!Q.empty()) {Edge temp=Q.top();Q.pop();if(vis[temp.to])continue;vis[temp.to]=true;for(int i=head[temp.to]; i!=-1; i=edge[i].next) {if(dis[edge[i].to]>dis[temp.to]+edge[i].val) {dis[edge[i].to]=dis[temp.to]+edge[i].val;Q.push(Edge(edge[i].to,0,dis[edge[i].to]));}}}if(dis[e]!=INF)return dis[e]/2;return -1; } map<int,int> mp[N]; int allPoint; int getPoint(int x,int y) {if (!mp[x][y])mp[x][y]=++allPoint;return mp[x][y]; } int main() {int n,m;scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));allPoint=n;for (int i=1; i<=m; i++) {int x,y,w;scanf("%d%d%d",&x,&y,&w);int newX=getPoint(x,w);int newY=getPoint(y,w);addEdge(x,newX,1);addEdge(newX,x,1);addEdge(newX,newY,0);addEdge(newY,newX,0);addEdge(y,newY,1);addEdge(newY,y,1);}int res=SPFA(1,n);printf("%d\n",res);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的すぬけ君の地下鉄旅行 / Snuke's Subway Trip（AtCoder-2069）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。