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

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

第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 的边。

  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 100000+1000 26  27 #define maxm 1000000+1000 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 struct edge{int go,next,w;}e[2*maxm]; 61  62 int n,m,k,s,t,tot,q[maxn],d[maxn],head[maxn]; 63  64 bool v[maxn]; 65  66 void insert(int x,int y,int z) 67  68 { 69  70     e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot; 71  72 } 73  74 void spfa() 75  76 { 77  78     for(int i=1;i<=n;++i) d[i]=inf; 79  80     memset(v,0,sizeof(v)); 81  82     int l=0,r=1,x,y;q[1]=s;d[s]=0; 83  84     while(l!=r) 85  86     { 87  88         x=q[++l];if(l==maxn)l=0;v[x]=0; 89  90         for(int i=head[x];i;i=e[i].next) 91  92          if(d[x]+e[i].w<d[y=e[i].go]) 93  94          { 95  96              d[y]=d[x]+e[i].w; 97  98              if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;} 99 100          }101 102     }103 104 }105 106 int main()107 108 {109 110     freopen("input.txt","r",stdin);111 112     freopen("output.txt","w",stdout);113 114     n=read();m=read();s=1;t=n;int x,y;115     for1(i,m)x=read(),y=read(),insert(x,y,read());116     spfa();117     printf("%d\n",d[t]);118 119     return 0;120 121 }