﻿ 2018 Multi-University Training Contest 7 Age of Moyu | 玄奇博客 # 2018 Multi-University Training Contest 7 Age of Moyu

### 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


### Source

2018 Multi-University Training Contest 7

chendu

### 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int INF = 0x7f7f7f7f;
const int  MAXN = 100100;
const int MAXM = 400100;
int Next[MAXM];
int dis[MAXN];
struct note{
int u,v,c;
note(){}
note(int u, int v, int c):u(u), v(v), c(c){}
} p[MAXM];

template<class T>
inline bool scan_d(T &ret){
char c;  int sgn;
if( c = getchar(), c==EOF) return 0;
while(c!='-' && (c <'0' || c>'9'))c = getchar();
sgn = (c=='-') ?-1:1;
ret = (c == '-')?0:(c-'0');
while(c = getchar(), c>='0' && c<='9') ret = ret*10+(c-'0');
ret *= sgn;
return 1;
}

inline void out(int x){
if(x > 9) out(x/10);
putchar(x%10+'0');
}
int e,n,m;
inline void addnote(int u, int v, int c){
p[e]=note(u,v,c);
}

inline bool relax(int u, int v, int c, int jvli){
if(dis[v] > jvli + c){
dis[v] = jvli + c;
return true;
}
if(dis[v] == jvli+c)return true;
return false;
}

inline void init(){
memset(Next, -1, sizeof(Next));
e=0;
for(int i=0; i<m; i++){
int u, v, c;
scan_d(u);scan_d(v);scan_d(c);
}
}

struct jiedian{
int dian;  int yuanxian;  int jvli;
jiedian(){}
jiedian(int dian, int yuanxian, int jvli):dian(dian),yuanxian(yuanxian), jvli(jvli){}
bool operator < (const jiedian &a)const{
return jvli > a.jvli;
}
};

int dyanse[MAXN];
inline bool spfa(int src){
memset(dyanse, 0, sizeof(dyanse));
for(int i=1; i<=n; i++)
dis[i] = INF;
dis[src] = 0;
dyanse=-1;
priority_queue<jiedian>que;  que.push(jiedian(src,-1, 0));
while(!que.empty()){
struct jiedian now = que.top();
int pre = now.dian;
int yanse = now.yuanxian;
int jvli = now.jvli;
if(pre == n) return true;
que.pop();
if(relax(pre, p[i].v, ((p[i].c==yanse)?0:1),jvli) ){
if(p[i].c == dyanse[p[i].v])continue;
dyanse[p[i].v]=p[i].c;
que.push(jiedian(p[i].v,p[i].c, dis[p[i].v]));
}
}
}
return true;
}

int main(){
//freopen("3.txt", "r", stdin);
while(scan_d(n)){
scan_d(m);
init();
spfa(1);
if(dis[n] == 0x7f7f7f7f)printf("-1\n");
else {
out(dis[n]);
putchar('\n');
}
}
}