bzoj2292 【POJ Challenge 】永远挑战

Description

lqp18_31和1tthinking经常出题来虐ftiasch。有一天, lqp18_31搞了一个有向图,每条边的长度都是1。 他想让ftiasch求出点1到点 N 的最短路。"水题啊。", ftiasch这么说道。

所以1tthinking把某些边的长度增加了1（也就是说，每条边的长度不是1就是2）。现在，可怜的ftiasch要向你求助了。

Input

 

第1行，两个整数 N (1 ≤ N ≤ 10⁵) 和 M (1 ≤ M ≤ 10⁶), 点和边的数量。

第2到 M + 1行: 三个整数 U_i, V_i, W_i (1 ≤ W_i ≤ 2), 从点 U_i 到 V_i 长度为 W_i 的边。

Output

 

一个整数，表示点1到点N的最短路。数据保证至少存在一条路径。

Sample Input

3 3
1 2 1
2 3 1
1 3 2

Sample Output

2

 

这题是要跑边权只有1和2的最短路

对于边权为2的边，可以添加一个“无用”的中间点使得边权变成只有1

然后sb搜索了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
	int to,next;
}e[2000010];
int head[1100010];
int q[2000010];
int dis[2000010];
int n,m,t,w,cnt,cnt2;
inline void ins(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
inline void bfs()
{
	t=0;w=1;
	q[1]=1;
	while (t<w)
	{
		int now=q[++t];
		for (int i=head[now];i;i=e[i].next)
		  if (dis[e[i].to]==-1)
		  {
		  	dis[e[i].to]=dis[now]+1;
		  	q[++w]=e[i].to;
		  }
	}
}
int main()
{
	n=cnt2=read();m=read();
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		if (z==1)ins(x,y);
		else
		{
			ins(x,++cnt2);
			ins(cnt2,y);
		}
	}
	for (int i=2;i<=cnt2;i++)dis[i]=-1;
	bfs();
	printf("%d
",dis[n]);
}