首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。