一个无向图 从s到t 有k个路可以权值为0 然后求最小值（我也不晓得描述的对不对）
50分做法：对于k=1的数据，起点跑一次SPFA，终点跑一次SPFA，然后枚举每条边a->b，用起点到a的最短路+终点到b的最短路更新ans即可
100分做法：把SPFA的距离数组改成2维的，令d[i][j]代表起点到点i用了j个急救包后的最短路 然后SPFA的松弛改成两种情况：用急救包和不用 最后的答案就是min{d[t][i]}(0<=i<=k)
upd19.9.3：
#include<bits/stdc++.h> using namespace std; #define ll long long #define Max(x,y) ((x)>(y)?(x):(y)) #define Min(x,y) ((x)<(y)?(x):(y)) typedef pair<int,int>pii; const int N=10000+50,M=50000+50,inf=0x3f3f3f3f; int n,m,k,s,t; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,w,nxt;}e[M<<1]; void add(int u,int v,int w){ e[++tot]=(edge){v,w,head[u]},head[u]=tot; } int dis[N][13]; bool vis[N][13]; struct node{ int id,bg,dis; bool operator <(const node&A)const{return dis>A.dis;} }; priority_queue<node> q; void spfa(){ while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); for(int i=0;i<=k;++i) dis[s][i]=0; q.push(node{s,0,0}); while(!q.empty()){ node nw=q.top();q.pop(); int u=nw.id,us=nw.bg; if(vis[u][us]) continue; vis[u][us]=1; for(int i=head[u],v,w;i;i=e[i].nxt){ v=e[i].v,w=e[i].w; if(dis[v][us]>dis[u][us]+w){ dis[v][us]=dis[u][us]+w; q.push(node{v,us,dis[v][us]}); } if(us+1<=k&&dis[v][us+1]>dis[u][us]){ dis[v][us+1]=dis[u][us]; q.push(node{v,us+1,dis[v][us+1]}); } } } } int main(){ //freopen("T3.txt","r",stdin); // freopen("move.out","w",stdout); rd(n),rd(m),rd(k),rd(s),rd(t); for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w); spfa(); int ans=inf; for(int i=0;i<=k;++i) ans=Min(ans,dis[t][i]); printf("%d",ans); return 0; }
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=10000+5,inf=0x3f3f3f3f; 4 int n,m,k,s,t,bag[N][15]; 5 inline int rd() 6 { 7 int x=0,w=0;char ch=0; 8 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 9 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 10 return w?-x:x; 11 } 12 13 int head[N<<1],cnt=0; 14 struct lxyy 15 { 16 int v,nxt,w,us; 17 }e[N*100]; 18 void add(int u,int v,int w) 19 { 20 e[++cnt].v=v; 21 e[cnt].w=w; 22 e[cnt].us=0; 23 e[cnt].nxt=head[u]; 24 head[u]=cnt; 25 } 26 struct node 27 { 28 int city,bag; 29 node():city(0),bag(0){}//无参初始化 30 node(int a,int b):city(a),bag(b){}//带参初始化 31 }; 32 int dis[N][15]; 33 void spfa(int S) 34 { 35 memset(dis,inf,sizeof(dis)); 36 for(int i=0;i<=k;i++) dis[S][i]=0; 37 deque<node> q; 38 q.push_back(node(S,0)); 39 while(!q.empty()) 40 { 41 node u=q.front(); 42 q.pop_front(); 43 for(int i=head[u.city];i;i=e[i].nxt) 44 { 45 int v=e[i].v,w=e[i].w,uss=u.bag; 46 if(dis[v][uss]>dis[u.city][uss]+w)//不用 47 { 48 dis[v][uss]=dis[u.city][uss]+w; 49 node vv;vv.bag=uss,vv.city=v; 50 if(!q.empty()) 51 { 52 node f=q.front(); 53 if(dis[v][uss]<=dis[f.city][f.bag]) q.push_front(vv); 54 else q.push_back(vv); 55 } 56 else q.push_back(vv); 57 } 58 if(uss+1<=k&&dis[v][uss+1]>=dis[u.city][uss])//用 59 { 60 dis[v][uss+1]=dis[u.city][uss]; 61 node vv;vv.city=v,vv.bag=uss+1; 62 if(!q.empty()) 63 { 64 node f=q.front(); 65 if(dis[v][uss+1]<=dis[f.city][f.bag]) q.push_front(vv); 66 else q.push_back(vv); 67 } 68 q.push_back(vv); 69 } 70 } 71 } 72 } 73 74 int main() 75 { 76 n=rd(),m=rd(),k=rd(); 77 s=rd(),t=rd(); 78 for(int i=1;i<=m;i++) 79 { 80 int u=rd(),v=rd(),w=rd(); 81 add(u,v,w);add(v,u,w); 82 } 83 spfa(s); 84 int ans=inf; 85 for(int i=0;i<=k;i++) 86 ans=min(ans,dis[t][i]); 87 printf("%d",ans); 88 return 0; 89 }