Problem 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.
Input
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.
Output
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.
Constraints
1 ≤ N, M ≤ 100000 = 105
1 ≤ Xi, Yi ≤ N
There can be multiple edges connecting the same pair of vertices, There can be self loops too i.e. Xi = Yi
Example
Input:
7 7
1 2
3 2
3 4
7 4
6 2
5 6
7 5
Output:
2
Explanation
We can consider two paths from 1 to 7:
1-2-3-4-7
1-2-6-5-7
In the first one we need to revert edges (3-2), (7-4). In the second one - (6-2), (5-6), (7-5). So the answer is min(2, 3) = 2.
题解
简单的最短路。spfa
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
using namespace std;
int n,m,head[MAXN],zz;
struct bian {int to,nx,v;} e[MAXN<<1];
int dis[MAXN],pd[MAXN],q[MAXN];
void insert(int x,int y)
{
zz++; e[zz].to=y; e[zz].v=0; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=1; e[zz].nx=head[y]; head[y]=zz;
}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++)
{scanf("%d%d",&x,&y);
insert(x,y);
}
}
void spfa()
{
memset(dis,127/3,sizeof(dis));
int t=0,w=1,i,p,x;
q[0]=1; pd[1]=1; dis[1]=0;
while(t!=w)
{x=q[t]; t=(t+1)%n;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].v)
{dis[p]=dis[x]+e[i].v;
if(!pd[p])
{pd[p]=1; q[w]=p; w=(w+1)%n;}
}
}
pd[x]=0;
}
if(dis[n]<=100000) printf("%d\n",dis[n]);
else printf("-1\n");
}
int main()
{
init(); spfa();
return 0;
}
dijkstra+堆。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
using namespace std;
int n,m,head[MAXN],zz;
struct bian {int to,nx,v;} e[MAXN<<1];
int size,pd[MAXN],dis[MAXN];
struct dui{int w,d;} q[MAXN*10];
//---------------------------------------------------------
void insert(int x,int y)
{
zz++; e[zz].to=y; e[zz].v=0; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=1; e[zz].nx=head[y]; head[y]=zz;
}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++)
{scanf("%d%d",&x,&y);
insert(x,y);
}
}
void heapfy(int x)
{
int l=x<<1,r=l+1,maxx=x;;
if(l<=size&&q[l].d<q[x].d) maxx=l;
if(r<=size&&q[r].d<q[maxx].d) maxx=r;
if(maxx!=x)
{swap(q[maxx],q[x]); heapfy(maxx);}
}
void del()
{
q[1]=q[size]; size--;
if(size) heapfy(1);
}
void weih(int x)
{
if(x<=1) return;
int i=x>>1;
if(q[i].d>q[x].d) swap(q[i],q[x]);
weih(i);
}
void dijkstra()
{
int i,x,p;
memset(dis,127/3,sizeof(dis));
size=1; q[1].w=1; q[1].d=0; dis[1]=0;
while(size)
{x=q[1].w; del();
if(pd[x]) continue;
pd[x]=1;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].v)
{dis[p]=dis[x]+e[i].v;
size++; q[size].d=dis[p]; q[size].w=p; weih(size);
}
}
}
if(dis[n]<=100000) printf("%d\n",dis[n]);
else printf("-1\n");
}
int main()
{
init(); dijkstra();
return 0;
}