HDU - 6386 Age of Moyu

Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting ofNN ports and MM shipping lines. The ports are numbered 11 to NN. Each line is occupied by a Weitian. Each Weitian has an identification number. 

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

When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 11XiangXiangJi. 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 11XiangXiangJi. In a case where Mr.Quin changed from some Weitian AA's line to another Weitian's line changes to Weitian AA's line again, the additional cost is incurred again. 

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

Input

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

For each test case,In the first line, two integers NN (2≤N≤100000)(2≤N≤100000) and MM (0≤M≤200000)(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 AiAi and BiBi of a shipping line (1≤Ai,Bi≤N)(1≤Ai,Bi≤N) and the third representing the identification number CiCi (1≤Ci≤1000000)(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 NN, output −1−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<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 200005;
const int maxm = 800005;
#define inf 0x3f3f3f3f
struct edge
{
	int to, ne, len;
}ed[maxm];
int d[maxn]; int cnt = 0;//计数
int m, n; int head[maxn];
struct *** {
	int u, pre, cost;
	bool operator < (const *** &a)const {
		return cost > a.cost;
	}
	***(int v, int pre, int cost) :u(v), cost(cost), pre(pre) {}
};
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int from, int to, int len) {
	ed[cnt].to = to; ed[cnt].len = len;
	ed[cnt].ne = head[from]; head[from] = cnt++;
}
int spfa() {
	priority_queue<***>q;
	for (int s = 1; s <= n; s++)
		d[s] = inf;
	q.push(***(1, -1, 0));
	d[1] = 0;
	while (!q.empty()) {
		*** t = q.top(); q.pop();
		if (t.cost > d[t.u])continue;
		if (t.u == n)return t.cost;
		for (int s = head[t.u]; ~s; s = ed[s].ne) {
			int w;
			if (ed[s].len == t.pre)w = d[t.u];
			else w = d[t.u] + 1;
			if (w < d[ed[s].to]) {
				d[ed[s].to] = w;
				q.push(***(ed[s].to, ed[s].len, w));
			}
		}
	}
	return -1;
}
int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		init();
		while (m--) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		printf("%d\n", spfa());
	}
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务