描述 Description
lqp18_31 和 1tthinking 经常出题来虐 ftiasch。有一天, lqp18_31 搞了一个有向图, 每条边的长度都是 1。 他想让 ftiasch 求出点 1 到点 N 的最短路。“水题啊。”, ftiasch 这么说道。
所以 1tthinking 把某些边的长度增加了 1（也就是说，每条边的长度不是 1 就是 2）。现在，可怜的 ftiasch 要向你求助了。
输入格式 InputFormat
第 1 行，两个整数 N (1 ≤ N ≤ 105) 和 M (1 ≤ M ≤ 106), 点和边的数量。
第 2 到 M + 1 行: 三个整数 Ui, Vi, Wi (1 ≤ Wi ≤ 2), 从点 Ui 到 Vi 长度为 Wi 的边。
输出格式 OutputFormat
一个整数，表示点 1 到点 N 的最短路。数据保证至少存在一条路径。
样例输入 SampleInput
3 3
1 2 1
2 3 1
1 3 2
样例输出 SampleOutput
2
把每个长度为 2 的边拆成两个边长为 1 的边，bfs 即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxm=2000005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,nx;
}e[maxm];
int head[maxm],dis[maxm];
int cnt;
deque <int> q;
inline void ins(int u,int v)
{
e[++cnt].to=v;e[cnt].nx=head[u];
head[u]=cnt;
}
inline void bfs(int s)
{
int i,u,v;
q.clear();
q.push_back(s);dis[s]=0;
while (!q.empty())
{
u=q.front();q.pop_front();
for (i=head[u];i;i=e[i].nx)
{
v=e[i].to;
if (!dis[v])
{
dis[v]=dis[u]+1;
if (v==n) return ;
q.push_back(v);
}
}
}
}
int main()
{
cnt=0;
scanf("%d%d",&n,&m);
t=n;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if (z==1) ins(x,y);
if (z==2)
{
t++;
ins(x,t);ins(t,y);
}
}
bfs(1);
printf("%d\n",dis[n]);
return 0;
}