首页 > 代码库 > CSU 1256 天朝的单行道

CSU 1256 天朝的单行道

2024-07-15 09:02:58   218人阅读

题目来源：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1256

     一个完全单向的有向图，最少更改多少条边能够从1到N。把原有的边的权值设为0，换方向的边的权值设为1。

简历邻接表。add_edge(u,v,0);add_edge(v,u,0);采用SPFA算法求出1->N权值最小的情况，即为要更改多少

条边，注意最多的边数是2*10000而不是10000，因为这个居然TE，真是奇怪，到最后找了好久才找到这个错误。

 1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #define INF 0x3f3f3f3f 5 const int maxn=5000+5,maxm=20000+5; 6 int first[maxn],next[maxm],v[maxm],w[maxm],dist[maxn],numedge; 7 bool done[maxn]; 8 void add_edge(int a,int b,int c) 9 {10     v[numedge]=b;11     next[numedge]=first[a];12     first[a]=numedge;13     w[numedge]=c;14     numedge++;15 }16 void spfa(void)17 {18     std::queue<int>q;19     q.push(1);20     done[1]=true;21     while(!q.empty()){22         int a=q.front();23         q.pop();24         done[a]=false;25         for(int e=first[a];e!=-1;e=next[e]){26             if(dist[v[e]]>dist[a]+w[e]){27                 dist[v[e]]=dist[a]+w[e];28                 if(!done[v[e]]){29                     q.push(v[e]);30                     done[v[e]]=true;31                 }32             }33         }34     }35 }36 int main()37 {38     int n,m;39     while(scanf("%d%d",&n,&m)!=EOF){40         memset(first,-1,sizeof(int)*(n+1));41         numedge=1;42         int a,b;43         for(int e=1;e<=m;e++){44             scanf("%d%d",&a,&b);45             add_edge(a,b,0);46             add_edge(b,a,1);47         }48         memset(done,false,sizeof(bool)*(n+1));49         for(int i=1;i<=n;i++)50             dist[i]=(i==1?0:INF);51         spfa();52         if(dist[n]>=INF)53             printf("-1\n");54         else55             printf("%d\n",dist[n]);56     }57     return 0;58 }

 


联系
我们