首页 > 代码库 > 【NOIP模拟题】行动！行动！（spfa+优化）
【NOIP模拟题】行动！行动！（spfa+优化）
spfa不加优化果断tle最后一个点。。。。。。。。。。。。。。。。。。。
这题和ch的一题很像，只不过这题简单点，这是一个层次图，即有很多个相同的图，这些相同的图之间又存在着练习。。
然后每一次队列存的状态是存两个信息的然后就玩了。。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <vector>#include <map>using namespace std;typedef long long ll;#define pii pair<int, int>#define mkpii make_pair<int, int>#define pdi pair<double, int>#define mkpdi make_pair<double, int>#define pli pair<ll, int>#define mkpli make_pair<ll, int>#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const ll getint() { ll r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const ll max(const ll &a, const ll &b) { return a>b?a:b; }inline const ll min(const ll &a, const ll &b) { return a<b?a:b; }const int N=50005, Q=1500005;const ll oo=~0ull>>2;int n, ihead[N], cnt, m, k, front, tail, vis[N][11];ll d[N][11];struct dat { int next, to; ll w; }e[N<<2];struct Queue { int u, k; }q[Q];void add(int u, int v, ll w) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w; e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u; e[cnt].w=w;}void spfa(int s) { rep(i, n) for1(j, 0, k) d[i][j]=oo; d[s][k]=0; q[tail++]=(Queue){s, k}; vis[s][k]=1; while(front!=tail) { int u=q[front].u, now=q[front++].k, v; if(front==Q) front=0; vis[u][now]=0; //dbg(u); dbg(now); dbg(d[u][now]); for(int i=ihead[u]; i; i=e[i].next) { v=e[i].to; if(d[v][now]>d[u][now]+e[i].w) { d[v][now]=d[u][now]+e[i].w; //dbg(v); dbg(now); dbg(d[v][now]); //puts("1"); dbg(v); dbg(now); dbg(d[v][now]); if(!vis[v][now]) { if(d[v][now]<d[q[front].u][q[front].k]) { --front; if(front<0) front+=Q; q[front]=(Queue){v, now}; } else { q[tail++]=(Queue){v, now}; vis[v][now]=1; if(tail==Q) tail=0; } } } if(now>0 && d[v][now-1]>d[u][now]) { d[v][now-1]=d[u][now]; //puts("2");dbg(v); dbg(now-1); dbg(d[v][now-1]); puts(""); if(d[v][now-1]<d[q[front].u][q[front].k]) { --front; if(front<0) front+=Q; q[front]=(Queue){v, now-1}; } else { q[tail++]=(Queue){v, now-1}; vis[v][now-1]=1; if(tail==Q) tail=0; } } } }}int main() { read(n); read(m); read(k); int s=getint(), t=getint(); for1(i, 1, m) { int u=getint(), v=getint(), w=getint(); add(u, v, w); } spfa(s); ll ans=oo; for1(i, 0, k) ans=min(ans, d[t][i]); printf("%lld\n", ans); return 0;}
题目描述：
大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 3
样例输出：
8
数据范围：
对于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.
【NOIP模拟题】行动！行动！（spfa+优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。