BZOJ_1614_ [Usaco2007_Jan]_Telephone_Lines_架设电话线_(二分+最短路_Dijkstra/Spfa)

描述

http://www.lydsy.com/JudgeOnline/problem.php?id=1614

分析

Dijkstra:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=1000+5,maxm=10000+5,INF=1<<30;
 5 int n,m,k,ect;
 6 int hd[maxn],f[maxm],d[maxn];
 7 bool vis[maxn];
 8 struct edge{
 9     int to,w,next;
10     edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
11     bool operator < (const edge &a) const { return w>a.w; }
12 }g[maxm<<1];
13 inline int read(int &x){ x=0;int k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')k=-1;for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x*=k; }
14 inline void add_edge(int u,int v,int w){
15     g[++ect]=edge(v,w,hd[u]); hd[u]=ect;
16     g[++ect]=edge(u,w,hd[v]); hd[v]=ect;
17 }
18 inline bool C(int x){
19     for(int i=1;i<=n;i++) d[i]=INF, vis[i]=false;
20     d[1]=0;
21     priority_queue <edge> q;
22     q.push(edge(1,0,0));
23     while(!q.empty()){
24         int u=q.top().to; q.pop();
25         if(vis[u]) continue;
26         vis[u]=true;
27         for(int i=hd[u];i;i=g[i].next){
28             int v=g[i].to,duv=g[i].w>x?1:0;
29             if(d[v]>d[u]+duv){
30                 d[v]=d[u]+duv;
31                 q.push(edge(v,d[v],0));
32             }
33         }
34     }
35     return d[n]<=k;
36 }
37 inline int bsearch(int l,int r){
38     if(!C(f[r])) return-1;
39     while(l<r){
40         int mid=l+(r-l)/2;
41         if(C(f[mid])) r=mid;
42         else l=mid+1;
43     }
44     return f[l];
45 }
46 int main(){
47     read(n); read(m); read(k);
48     for(int i=1,u,v,w;i<=m;i++){
49         read(u); read(v); read(w);
50         add_edge(u,v,w);
51         f[i]=w;
52     }
53     sort(f+1,f+1+m);
54     printf("%d
",bsearch(0,m));
55     return 0;
56 }

View Code

Spfa:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=1000+5,maxm=10000+5,INF=1<<30;
 5 int n,m,k,ect;
 6 int hd[maxn],q[maxn],f[maxm],d[maxn];
 7 bool vis[maxn];
 8 struct edge{
 9     int to,w,next;
10     edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
11 }g[maxm<<1];
12 inline int read(int &x){ x=0;int k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')k=-1;for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x*=k; }
13 inline void add_edge(int u,int v,int w){
14     g[++ect]=edge(v,w,hd[u]); hd[u]=ect;
15     g[++ect]=edge(u,w,hd[v]); hd[v]=ect;
16 }
17 inline bool C(int x){
18     for(int i=1;i<=n;i++) d[i]=INF, vis[i]=false;
19     d[1]=0,vis[1]=true;
20     int l=0,r=0;
21     q[r++]=1;
22     while(l!=r){
23         int u=q[l++]; if(l==maxn-1) l=0;
24         vis[u]=false;
25         for(int i=hd[u];i;i=g[i].next){
26             int v=g[i].to,duv=g[i].w>x?1:0;
27             if(d[v]>d[u]+duv){
28                 d[v]=d[u]+duv;
29                 if(!vis[v]){
30                     q[r++]=v; if(r==maxn-1) r=0;
31                     vis[v]=true;
32                 }
33             }
34         }
35     }
36     return d[n]<=k;
37 }
38 inline int bsearch(int l,int r){
39     if(!C(f[r])) return-1;
40     while(l<r){
41         int mid=l+(r-l)/2;
42         if(C(f[mid])) r=mid;
43         else l=mid+1;
44     }
45     return f[l];
46 }
47 int main(){
48     read(n); read(m); read(k);
49     for(int i=1,u,v,w;i<=m;i++){
50         read(u); read(v); read(w);
51         add_edge(u,v,w);
52         f[i]=w;
53     }
54     sort(f+1,f+1+m);
55     printf("%d
",bsearch(0,m));
56     return 0;
57 }

View Code