bzoj 2763: [JLOI2011]飞行路线

绝地灬酷狼 2022-01-10 19:55 255阅读 0赞

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 #include<queue>
     5 #define pa pair<int,int>
     6 #define inf 0x7fffffff
     7 #define M 400008
     8 using namespace std;
     9 int d[M],f[M],n,m,k,s,t,cnt,head[M],next[10*M],u[10*M],v[10*M];
    10 void jia(int a1,int a2,int a3)
    11 {
    12     cnt++;
    13     next[cnt]=head[a1];
    14     head[a1]=cnt;
    15     u[cnt]=a2;
    16     v[cnt]=a3;
    17     return;
    18 }
    19 int main()
    20 {
    21     scanf("%d%d%d",&n,&m,&k);
    22     scanf("%d%d",&s,&t);
    23     for(int i=1;i<=m;i++)
    24       {
    25         int a1,a2,a3;
    26         scanf("%d%d%d",&a1,&a2,&a3);
    27         jia(a1,a2,a3);
    28         jia(a2,a1,a3);
    29         for(int j=1;j<=k;j++)
    30           {
    31             jia(j*n+a1,j*n+a2,a3);
    32             jia(j*n+a2,j*n+a1,a3);
    33             jia((j-1)*n+a1,j*n+a2,0);
    34             jia((j-1)*n+a2,j*n+a1,0);
    35           }
    36       }
    37     priority_queue<pa,vector<pa>,greater<pa> >q;
    38     memset(d,60,sizeof(d));
    39     q.push(make_pair(0,s));
    40     d[s]=0;
    41     for(;!q.empty();)
    42       {
    43         int now=q.top().second;
    44         q.pop();
    45         if(f[now])
    46           continue;
    47         f[now]=1;
    48         for(int i=head[now];i;i=next[i])
    49           if(d[u[i]]>d[now]+v[i])
    50             {
    51                 d[u[i]]=d[now]+v[i];
    52                 q.push(make_pair(d[u[i]],u[i]));
    53             }
    54       }
    55     int ans=inf;
    56     for(int i=0;i<=k;i++)
    57       ans=min(ans,d[i*n+t]);
    58     printf("%d\n",ans);
    59     return 0;
    60 }

分层图按k分层

转载于:https://www.cnblogs.com/xydddd/p/5304573.html