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 73 74 75 76
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #include <queue> #define INF 1010000000 using namespace std; typedef long long ll; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } struct Edge{ int to,_next,cost; }; struct Node{ int h,e,dis; Node(int h_,int e_,int d_){ h=h_,e=e_,dis=d_; } Node(){} }; bool operator <(const Node &n1,const Node &n2){ return n1.dis>n2.dis; } priority_queue<Node> pq; Edge edge[100005]; int n,m,k,at[10005]={0},F[10005][21]={0},cnt=0; void addedge(int u,int v,int c){ edge[++cnt].to=v, edge[cnt].cost=c, edge[cnt]._next=at[u], at[u]=cnt; } void Dij(){ F[1][0]=0,pq.push(Node(1,0,0)); Node tmp; int h_,e_,d_,v_,c_; while(!pq.empty()){ tmp=pq.top(),pq.pop(); if(tmp.dis>F[tmp.h][tmp.e])continue; h_=tmp.h,e_=tmp.e,d_=tmp.dis; for(int i=at[h_];i;i=edge[i]._next){ v_=edge[i].to,c_=edge[i].cost; if(F[v_][e_]>F[h_][e_]+c_) F[v_][e_]=F[h_][e_]+c_, pq.push(Node(v_,e_,F[v_][e_])); if(e_<k&&F[v_][e_+1]>F[h_][e_]) F[v_][e_+1]=F[h_][e_], pq.push(Node(v_,e_+1,F[v_][e_+1])); } } } void init(){ n=read(),m=read(),k=read(); int u,v,c; for(int i=1;i<=m;i++){ u=read(),v=read(),c=read(); addedge(u,v,c),addedge(v,u,c); } } void solve(){ memset(F,0x3F,sizeof(F)); Dij(); int ans=INF*2; for(int i=0;i<=k;i++)ans=min(ans,F[n][i]); printf("%dn",ans); } int main(){ init(); solve(); return 0; }
|
近期评论