【bfs】极其简单的最短路问题

现在假设每条道路需要花费小X的时间为1，由于有数以万计的好朋友沿路祝贺，导致小X在通过某些路不得不耗费1的时间来和他们聊天，尽管他希望尽早见到小C，所以他希望找到一条最快时间到达电影院的路。 一开始小X在1号点，共有N个点，M条路，电影院为T号点。

Input

第一行2个正整数，分别为n，m，t 以下m行，每行3个数，表示连接的编号以及权值 （注意，可能会有重边）

Output

一行一个数，表示1到t的最短路

---

由于边长只能会是1或者2，所以边长为2的就新建一个点，然后以新点为中介连接俩个点就行了。 然后bfs。

#include<cstdio> #include<queue> using namespace std; int n,m,t,b[5000001],l[5000001],tt; struct asdf{ int to,next; } a[20000001]; int read(){ int l=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9'){ l=l*10+c-48; c=getchar(); } return l; } void add(int xx,int yy){ a[++tt].to=yy; a[tt].next=l[xx]; l[xx]=tt; a[++tt].to=xx; a[tt].next=l[yy]; l[yy]=tt; } void bfs(){ b[1]=1; queue<int> Q; Q.push(1); while(Q.size()){ int d=Q.front(); Q.pop(); for(int i=l[d];i;i=a[i].next) if(b[a[i].to]==0){ b[a[i].to]=b[d]+1; Q.push(a[i].to); } if(b[t]>0) { printf("%d",b[t]-1); return; } } } int main(){ n=read(); m=read(); t=read(); int x,y; for(int i=1;i<=m;++i){ x=read(); y=read(); if(read()==1) add(x,y); else add(x,++n),add(n,y); } bfs(); }