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());
	}
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:20
点赞 评论 收藏
分享
06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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