题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2763
一眼分层图….
一不小心又当成单向边了..
|
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 |
#include<bits/stdc++.h> #define MAXN 10010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int to,len; node(){} node(int a,int b){to=a,len=b;} }; struct node1{ int now,d; node1(int a,int b){d=a,now=b;} node1(){} }; int n,m,k,s,t,ans=100000000; vector<node>v[MAXN]; int dis[11][MAXN]; bool vis[11][MAXN]; queue<node1>q; int main(){ n=rd(),m=rd(),k=rd(); s=rd(),t=rd(); while(m--){ int x=rd(),y=rd(),z=rd(); v[x].push_back(node(y,z)); v[y].push_back(node(x,z)); } memset(dis,0x3f3f3f3f,sizeof(dis)); dis[0][s]=0; vis[0][s]=1; q.push(node1(0,s)); while(!q.empty()){ node1 tmp=q.front(); int now=tmp.now; int d=tmp.d; q.pop(); if(now==t){ ans=min(ans,dis[d][now]); continue; } for(int i=0; i<v[now].size(); i++){ int to=v[now][i].to; int len=v[now][i].len; if(d<k && dis[d+1][to]>dis[d][now]){ dis[d+1][to]=dis[d][now]; if(!vis[d+1][to])q.push(node1(d+1,to)); } if(dis[d][to]>dis[d][now]+len){ dis[d][to]=dis[d][now]+len; if(!vis[d][to])q.push(node1(d,to)); } } vis[d][now]=0; } printf("%d\n",ans); return 0; } |
