记录编号	535648	评测结果	AAAAAAAAAA
题目名称	[JLOI 2011] 飞行路线	最终得分	100
用户昵称	雾茗	是否通过	通过
代码语言	C++	运行时间	0.948 s
提交时间	2019-07-05 16:03:25	内存使用	6.37 MiB

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(1)
#include<bits/stdc++.h>
#define ll long long
const int M=1e4+10;
inline ll read(){
    ll x=0,f=1; 
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
int dis[M][12];
int n,m,k,s,t,cnt;
int in[M][12],head[M];
struct edge{
    int to,val,next;
}e[M*5<<1];
void add(int u,int v,int w){
    e[++cnt].to=v; 
    e[cnt].val=w; 
    e[cnt].next=head[u]; 
    head[u]=cnt;
}
struct pos{
    int id,num;
    friend bool operator < (const pos x,const pos y){
        return x.num>y.num;
    }
}nd;
void dj(){
    nd.id=s; 
    nd.num=0;
    std::priority_queue<pos> Q;
    Q.push(nd); 
    in[s][0]=1;
    while(!Q.empty()){
        pos tmp=Q.top();
        int u=tmp.id,g=tmp.num;
        if(in[u][g]==0) continue;
        in[u][g]=0; 
        Q.pop();
        if(dis[u][g]>=dis[t][k]) continue;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to,w=e[i].val;
            if(dis[v][g]>dis[u][g]+w){
                dis[v][g]=dis[u][g]+w;
                if(!in[v][g]){
                    in[v][g]=1;
                    pos newp; newp.id=v,newp.num=g;
                    Q.push(newp);
                }
            }
            if(g<k&&dis[v][g+1]>dis[u][g]){
                dis[v][g+1]=dis[u][g];
                if(!in[v][g+1]){
                    in[v][g+1]=1;
                    pos newp; 
                    newp.id=v;
                    newp.num=g+1;
                    Q.push(newp);
                }
            }
        }
    }
}
int mn(){
	freopen("moved.in","r",stdin);
	freopen("moved.out","w",stdout);
    n=read(); 
    m=read(); 
    k=read();
    s=read(); 
    t=read();
    memset(dis ,0x3f, sizeof(dis));
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        add(u,v,w); 
        add(v,u,w);
    }
    dis[s][0]=0; 
    dj();
    for(int i=1;i<=k;++i)
    	dis[t][k]=std::min(dis[t][i],dis[t][k]);
    printf("%d\n",dis[t][k]);
}
int lll=mn();
int main(){;}