首页 > 代码库 > CSUOJ 1256
CSUOJ 1256
解法:
对u->v的边 add_edge(u,v,0)
增加一条u->v反向边 add_edge(v,u,1)
求一遍1->n的最短路
#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;
#define M 20010 //用了几次 10010 RE了。。。。。。
#define N 5010
const int inf = 0x3f3f3f3f;
int w[M],d[N],v[M],u[M],next[M],first[N],e;
bool inq[N];
void init(){
e=0;
memset(first,-1,sizeof(first));
memset(d,0x3f,sizeof(d));
}
void addedge(int a,int b,int x){
v[e]=b;
next[e]=first[a];
w[e]=x;
first[a]=e++;
}
void SPFA(int st){
queue<int> q;
d[st]=0;
q.push(st);
inq[st]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=first[u];i!=-1;i=next[i]){
if(d[v[i]]>d[u]+w[i]){
d[v[i]]=d[u]+w[i];
if(!inq[v[i]]){q.push(v[i]);inq[v[i]] = 1;}
}
}
}
}
int main(){
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
addedge(a,b,0);
addedge(b,a,1);
}
SPFA(1);
if(d[n]!=inf)printf("%d\n",d[n]);
else printf("-1\n");
}
}