描述 Description
Sometimes mysteries happen. Chef found a directed graph with N vertices and M edges in his kitchen! The evening was boring and chef has nothing else to do, so to entertain himself, Chef thought about a question “What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N.
输入格式 InputFormat
Each test file contains only one test case.
The first line of the input contains two space separated integers N and M, denoting the number of vertices and the number of edges in the graph respectively. The ith line of the next M lines contains two space separated integers Xi and Yi, denoting that the ith edge connects vertices from Xi to Yi.
输出格式 OutputFormat
In a single line, print the minimum number of edges we need to revert. If there is no way of having at least one path from 1 to N, print -1.
样例输入 SampleInput
7 7
1 2
3 2
3 4
7 4
6 2
5 6
7 5
样例输出 SampleOutput
2
代码 Code
建边然后跑最短路。。。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <deque>
using namespace std;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[200005];
int head[100005],dis[100005];
bool used[100005];
int cnt;
deque <int> q;
inline void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
inline void spfa(int s)
{
int i,j,t,u,v,w;
while (!q.empty()) q.pop_front();
memset(used,false,sizeof(used));
for (i=1;i<=n;i++) dis[i]=inf;
q.push_back(s);dis[s]=0;used[s]=true;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (cnt=0,i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(x,y,0);
insert(y,x,1);
}
spfa(1);
printf("%d\n",(dis[n]==inf)?-1:dis[n]);
return 0;
}