[USACO08JAN]电话线Telephone Lines

【TimeGate】

https://www.luogu.org/problem/P1948

【解题思路】

本题的解法：二分答案+spfa

【code】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int a,b,l,c,i,j,k,n,K,p,mid,nxt[20005],t=0,w[20005],h[20005],endd[20005],dis[20005],ans,leftt,rightt;
 7 bool lastt[20005],ok;
 8 void add(int u,int v,int x) {
 9     t++;
10     nxt[t]=h[u];
11     h[u]=t;
12     w[t]=x;
13     endd[t]=v;
14 }
15 bool SPFA(int x){
16     for(i=1;i<=n;i++){
17         lastt[i]=false;
18         dis[i]=1<<30;
19     }
20     ok=true;
21     dis[1]=0,lastt[1]=true;
22     while(ok){
23         ok=false;
24         for(j=1;j<=n;j++)
25             if(lastt[j]==true){
26               lastt[j]=false;
27               for(k=h[j];k!=-1;k=nxt[k])
28                   if(dis[endd[k]]>dis[j]+(w[k]>x?1:0)){
29                    dis[endd[k]]=dis[j]+(w[k]>x?1:0);
30                    lastt[endd[k]]=true;
31                    ok=true;
32                   }
33             }
34     }
35     if(dis[n]==1<<30){
36         printf("-1\n");
37         exit(0);
38     }
39     return dis[n]<=K;
40 }
41 int main(){
42     //freopen("telephone.in","r",stdin);
43     //freopen("telephone.out","w",stdout);
44     scanf("%d%d%d",&n,&p,&K);
45     memset(nxt,-1,sizeof(nxt));
46     for(i=1;i<=p;i++){
47         scanf("%d%d%d",&a,&b,&l);
48         add(a,b,l);
49         add(b,a,l);
50         if(l>rightt)rightt=l;
51     }
52     leftt=0;
53     while(leftt<rightt){
54         mid=(leftt+rightt)/2;
55         if(SPFA(mid))rightt=mid;
56         else leftt=mid+1;
57     }
58     printf("%d\n",rightt);
59     /*for(i=1;i<=n;i++)
60         printf("%d %d\n",i,SPFA(i));
61  */
62     return 0;
63 }