首页 > 其他 > 详细

CSU 1256 天朝的单行道

时间:2014-08-01 22:57:32      阅读:451      评论:0      收藏:0      [点我收藏+]

题目来源: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         else
55             printf("%d\n",dist[n]);
56     }
57     return 0;
58 }

 

CSU 1256 天朝的单行道,布布扣,bubuko.com

CSU 1256 天朝的单行道

原文:http://www.cnblogs.com/BMESwimming/p/3885837.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!