「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 ≤ 105) 和 M (1 ≤ M ≤ 106), 点和边的数量。
第2到 M + 1行: 三个整数 Ui, Vi, Wi (1 ≤ Wi ≤ 2), 从点 Ui 到 Vi 长度为 Wi 的边。
Output
一个整数，表示点1到点N的最短路。数据保证至少存在一条路径。
Sample Input
3 3
1 2 1
2 3 1
1 3 2
1 2 1
2 3 1
1 3 2
Sample Output
2
题解
如果a到b的边权为2，建一个新的点c，a向c连边，c向b连边
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,cnt,last; int head[1100001],q[1100001],dis[1100001]; struct data{int to,next;}e[2000001]; void insert(int u,int v) {cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void bfs() { memset(dis,-1,sizeof(dis)); int t=0,w=1,now; q[0]=1;dis[1]=0; while(t<w) { now=q[t];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() { scanf("%d%d",&n,&m); last=n; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(w==1)insert(u,v); else {insert(u,++n);insert(n,v);} } bfs(); printf("%d",dis[last]); return 0; } |
Subscribe
计数器 9788195
OI 课件=>
OI 课件=>