[BZOJ 2662]冻结

danihao123 posted @ 2016年8月24日 13:38 in 题解 with tags BZOJ WC 分层图最短路 最短路 Dijkstra , 618 阅读
转载请注明出处:http://danihao123.is-programmer.com/

又是一道分层图最短路水题……

我估计会卡SPFA(或许可能不卡?),所以再次写了pb_ds优化Dijkstra。

代码:

/**************************************************************
    Problem: 2662
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:868 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=51,maxk=51,maxm=2005;
int cnt=0;
int first[maxn];
int to[maxm],next[maxm];
int dist[maxm];
inline void Add_Edge(int x,int y,int z){
    cnt++;
    next[cnt]=first[x];
    first[x]=cnt;
    to[cnt]=y;
    dist[cnt]=z;
}
 
int d[maxn][maxk];
bitset<maxn> vis[maxk];
struct Node{
    int x,k,d;
    bool operator <(const Node& itt) const{
        return d<itt.d;
    }
    bool operator >(const Node& itt) const{
        return d>itt.d;
    }
};
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
inline void relax(int x,int y,int p){
    d[x][y]=p;
    if(ite[x][y]!=0)
        Q.modify(ite[x][y],(Node){x,y,p});
    else
        ite[x][y]=Q.push((Node){x,y,p});
}
int dij(){
    register int i,u,v,ans=0x7f7f7f7f;
    memset(d,0x7f,sizeof(d));
    d[1][0]=0;
    ite[1][0]=Q.push((Node){1,0,0});
    while(!Q.empty()){
        u=Q.top().x;
        v=Q.top().k;
        Q.pop();
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[to[i]][v+1]>(d[u][v]+dist[i]/2)){
                    relax(to[i],v+1,d[u][v]+dist[i]/2);
                }
            }
            if(d[to[i]][v]>d[u][v]+dist[i]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    for(i=0;i<=k;i++)
        ans=min(ans,d[n][i]);
    return ans;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    k=readint();
    for(i=1;i<=m;i++){
        u=readint();
        v=readint();
        d=readint();
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    writeint(dij());
    putchar('\n');
    return 0;
}
ekalyan-epass.in 说:
Jul 05, 2023 08:26:26 PM

Strives to provide better service in a variety of ways, however aside from the public information you choose to share, we do not sell or otherwise distribute your personal information.We are very aware of email spam and make every effort to protect every email ekalyan-epass.in be seen by the public.strives to provide better service in several ways, and we don't sell or give away your personal information unless you voluntarily make it public. We are very aware of email spam and make every effort to protect every email.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter