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-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
06-20 21:22
已编辑
门头沟学院 Java
纯真的河老师在喝茶:答应了就跑啊,实习随便跑啊,别被pua了,md就是找个廉价劳动力,还平稳过度正式工,到时候跟你说没转正
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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