首页 > 代码库 > csuoj 1256

csuoj 1256

题意:给出一张有向图,问最少改变多少条边的方向,使得图中存在一条从1到N的路径

思路:原本有的路径权值为0,新加一个反向的路径,权值为1,这样只要走一次新加的路径,最短路就会加1,最后的长度就是新加路径的个数了

  

#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define MAX 20010#define inf 0x3f3f3f3fint n,m;int first[MAX],d[MAX],inq[MAX],w[MAX],v[MAX],next[MAX],e;void init(){    e =0 ;    memset(first,-1,sizeof(first));}void add_edge(int a,int b,int c){    v[e] = b;    next[e] = first[a];    w[e] = c;    first[a]= e++;}void spfa(int src){    queue<int>q;    memset(d,0x3f,sizeof(d));    d[src]= 0,inq[src] = 1;    q.push(src);    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(){    while(cin>> n>> m)    {        init();        for(int i=0;i< m;i++)        {            int a,b;            cin >> a>>b;            add_edge(a,b,0);            add_edge(b,a,1);        }        spfa(1);        if(d[n]!= inf)cout<<d[n]<< endl;        else cout<< "-1"<< endl;    }    return 0;}