网站开发主要创新点,微信开放平台怎么解除,儿童摄影设计,mvc网站建设的实验报告给定一个 nn 个点 mm 条边的有向图#xff0c;图中可能存在重边和自环。
所有边的长度都是 11#xff0c;点的编号为 1∼n1∼n。
请你求出 11 号点到 nn 号点的最短距离#xff0c;如果从 11 号点无法走到 nn 号点#xff0c;输出 −1−1。
输入格式
第一行包含两个整数…给定一个 nn 个点 mm 条边的有向图图中可能存在重边和自环。
所有边的长度都是 11点的编号为 1∼n1∼n。
请你求出 11 号点到 nn 号点的最短距离如果从 11 号点无法走到 nn 号点输出 −1−1。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 mm 行每行包含两个整数 aa 和 bb表示存在一条从 aa 走到 bb 的长度为 11 的边。
输出格式
输出一个整数表示 11 号点到 nn 号点的最短距离。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例
4 5
1 2
2 3
3 4
1 3
1 4输出样例
1
#includebits/stdc.h
using namespace std;
const int N 100010;
int h[N],e[N],ne[N],idx;//邻接表数据结构
int d[N],st[N];
int n,m;
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
void bfs()
{memset(d,0x3f,sizeof d);d[1]0;st[1]1;queueint q;q.push(1);while(q.size()){int tq.front();q.pop();for(int ih[t];i!-1;ine[i]){int je[i];if(!st[j]){d[j]d[t]1;q.push(j);st[j]1;}}}
}
int main()
{cinnm;memset(h,-1,sizeof h);for(int i0;im;i){int a,b;cinab;add(a,b);}bfs();cout (d[n] 0x3f3f3f3f ? -1 : d[n]);//如果到n号节点的距离不是无穷大输出距离如果是无穷大输出-1.
}
