1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
template <typename T>inline void (T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
int nxt[N],head[N],w[N],v[N],dis[N][13],vis[N][13];
int n,m,h,cnt,s,t;
inline void adde(int a,int b,int c){
v[++cnt]=b;
w[cnt]=c;
nxt[cnt]=head[a];
head[a]=cnt;
}
struct node{
int d,u,id;
node(int a=0,int b=0,int c=0):d(a),u(b),id(c){}
bool operator<(const node &a)const {return d>a.d;}
};
priority_queue<node> q;
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(node(0,s,0));
while(!q.empty()){
node a=q.top();
q.pop();
int ds=a.d,u=a.u,id=a.id;
if(vis[u][id])continue;
vis[u][id]=1;
for(int i=head[u];i;i=nxt[i]){
int k=v[i],c=w[i];
if(id<h&&!vis[k][id+1]&&dis[k][id+1]>ds){
dis[k][id+1]=ds;
q.push(node(ds,k,id+1));
}
if(!vis[k][id]&&dis[k][id]>ds+c){
dis[k][id]=ds+c;
q.push(node(dis[k][id],k,id));
}
}
}
}
int main(){
read(n);read(m);read(h);
read(s);read(t);
rep(i,1,m){
int a,b,c;
read(a);read(b);read(c);
adde(a,b,c);
adde(b,a,c);
}
dijkstra();
int ans=0x3f3f3f3f;
rep(i,0,h)ans=min(ans,dis[t][i]);
printf("%dn",ans);
return 0;
}
|
近期评论