大CX国的大兵Jack接到一项任务：敌方占领了n座城市（编号0~n-1），有些城市之间有双向道路相连。Jack需要空降在一个城市S，并徒步沿那些道路移动到T城市。虽然Jack每从一个城市到另一个城市都会受伤流血，但大CX国毕竟有着“过硬”的军事实力，它不仅已经算出Jack在每条道路上会损失的血量，还给Jack提供了k个“简易保护罩”，一个保护罩可以让Jack在一条路上的流血量为0。Jack想知道自己最少会流多少血，不过他毕竟是无脑的大兵，需要你的帮助。
第一行有三个整数n,m,k，分别表示城市数，道路数和保护罩个数。
第二行有两个整数，S,T。分别表示Jack空降到的城市编号和最终要到的城市。
接下来有m行，每行三个整数a,b,c，表示城市a与城市b之间有一条双向道路。
Jack最少要流的血量。
5 6 1
0 3
3 4 5
0 1 5
0 2 100
1 2 5
2 4 5
2 4 38时间：1s 空间：128M
对于30%的数据,2<=n<=50, 1<=m<=300, k=0;
对于50%的数据,2<=n<=600, 1<=m<=6000, 0<=k<=1;
对于100%的数据,2<=n<=10000, 1<=m<=50000, 0<=k<=10.
Server time: 2020-10-26 18:26:14 | 开源项目
题解: 40分做法：没有药包时朴素spfa就ok，如果仅有一个药包枚举边，删边加边就ojbk
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=100003; const int oo=0x3f3f3f3f; int n,m,K,cnt,x,y,z,S,T; int vis[N],head[N]; ll dis[N],ans=oo; struct node{ int to,next,w; }e[N]; void add(int u,int v,int w){ e[++cnt].to=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } ll spfa(int s,int t){ queue<int>q; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } if(dis[t]!=oo) return dis[t]; else return -1; } int main(){ freopen("gogo.in","r",stdin); freopen("gogo.out","w",stdout); scanf("%d %d %d",&n,&m,&K); scanf("%d %d",&S,&T); for(int i=1;i<=m;i++){ scanf("%d %d %d",&x,&y,&z); add(x,y,z); add(y,x,z); } if(K==0) { printf("%d\n",spfa(S,T)); return 0; } if(K==1) { for(int i=1;i<=cnt;i+=2){ int yc=e[i].w; e[i].w=0; e[i+1].w; ans=min(ans,spfa(S,T)); e[i].w=yc; e[i+1].w=yc; } printf("%lld\n",ans); return 0; } return 0; }
原文：https://www.cnblogs.com/wuhu-JJJ/p/13880049.html