M_sea

洛谷4822 [BJWC2012]冻结
LuoguBZOJ分析出题人绝对是车万厨设$dis[i][j]$表示到$i$点用了$j$张SpellCard的最短...
扫描右侧二维码阅读全文
13
2019/02

洛谷4822 [BJWC2012]冻结

Luogu

BZOJ

分析

出题人绝对是车万厨

设$dis[i][j]$表示到$i$点用了$j$张SpellCard的最短时间。

跑一遍$\texttt{Dijkstra}$就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10;
const int M=1000+10;

int n,m,k;

struct Edge { int v,w,nxt; };
Edge e[M<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

struct HeapNode {
    int u,s,d;
    bool operator <(const HeapNode& x) const {
        return d>x.d;
    }
};

priority_queue<HeapNode> Q;
int dis[N][N];

inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis)); dis[1][0]=0;
    Q.push((HeapNode){1,0,0});
    while (!Q.empty()) {
        HeapNode x=Q.top(); Q.pop();
        int u=x.u,s=x.s,d=x.d;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (d+w<dis[v][s])
                dis[v][s]=d+w,Q.push((HeapNode){v,s,dis[v][s]});
            if (s<k&&d+w/2<dis[v][s+1])
                dis[v][s+1]=d+w/2,Q.push((HeapNode){v,s+1,dis[v][s+1]});
        }
    }
}

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dijkstra();
    int ans=0x3f3f3f3f;
    for (re int i=0;i<=k;++i) ans=min(ans,dis[n][i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 02 月 13 日 10 : 08 AM

发表评论