行动! 行动! (move)
题目描述
大 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 \leq n \leq 50, 1 \leq m \leq 300, k = 0\);
对于 50% 的数据,\(2 \leq n \leq 600, 1 \leq m \leq 6000, 0 \leq k \leq 1\);
对于 100% 的数据,\(2 \leq n \leq 10000, 1 \leq m \leq 50000, 0 \leq k \leq 10\).
Explanation
简单建边, 因为做法和题解一样 (但是为什么 SPFA 总是写挂), 所以还是照样粘题解.
分层图的最短路.
K=1 时可以考虑将一点拆成两点. 两层分别按原图建图, 然后在第一层向第二层中对应的点连一条长度为 0 的单向边, 例如原图有一条 1 到 2 的双向边. 将 1 拆成 1 和 1+n, 2 同理, 然后分别在 1、2 和 1+n、2+n 之间建原长度的双向边, 然后分别在 1、2+n 和 2、1+n 之间建一条长度为 0 的单向边, 这样的图能保证至多跑一次长度为 0 的边. 在点数边数较少的情况下, K 大到 3, 4 应该也能卡过.
至于正解, 可以用一个二维的 dis 数组跑最短路, dis [i] [j] 表示到达 i 点, 用了 j 次急救包. 用最短路做一个类似于 dp 的东西. 答案为 dis [T] [K].
注意: 裸跑 spfa 会 T 三个点, 若写 spfa 记得加 SLF 优化.
话说最短路最后没有调出来, 所以就暂时搁在这里. 底下源码区写的是 STD 代码.
写挂的错误代码:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long lli;
const int maxn = 100100, maxm = 500100;
const lli infinit = 0x007f7f7f7f7f7f7fll;
class ShortestPath
{
public:
struct edge
{
int u, v;
lli len;
edge *next;
} *edges[maxn], epool[maxm];
int n, s, t, ecnt;
void addedge(int u, int v, lli len)
{
edge *p = &epool[++ecnt],
*q = &epool[++ecnt];
p->u = u; p->v = v; p->len = len;
p->next = edges[u]; edges[u] = p;
q->u = v; q->v = u; q->len = len;
q->next = edges[v]; edges[v] = q;
return ;
}
void eval(void)
{
throw ;
}
};
class n_queue
{
public:
priority_queue< pair<int, int> > pq;
void push(int first, int second) {
this->pq.push( make_pair(-second, first) ); }
void pop(void) {
this->pq.pop(); }
int top(void) {
return this->pq.top().second; }
int get(void) {
int res = this->top();
this->pop();
return res; }
bool empty(void) {
return this->pq.empty(); }
};
class HeapedDijkstra : public ShortestPath
{
public:
lli dist[maxn];
bool inque[maxn];
lli eval(void)
{
// n_queue que;
queue<int> que;
for (int i = 1; i <= n; i++)
inque[i] = false, dist[i] = infinit;
inque[s] = true;
dist[s] = 0;
// que.push(s, 0);
que.push(s);
while (!que.empty()) {
// int p = que.get();
int p = que.front();
que.pop();
printf("relaxing %d\n", p);
for (edge *ep = edges[p]; ep; ep = ep->next)
if (dist[p] + ep->len < dist[ep->v]) {
dist[ep->v] = dist[p] + ep->len;
if (!inque[ep->v]) {
// que.push(ep->v, dist[ep->v]);
que.push(ep->v);
inque[ep->v] = true;
}
}
inque[p] = false;
}
return dist[t];
}
// lllll
} graph;
int n, m, K, S, T;
int main(int argc, char** argv)
{
// Let's give it a test.
/*
scanf("%d%d", &n, &m);
for (int i = 1, a, b, c; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
graph.addedge(a, b, c);
}
graph.n = n;
graph.s = 1;
graph.t = n;
graph.eval();
printf("Result is: %d\n", graph.dist[n]);
return 0;
*/
scanf("%d%d%d", &n, &m, &K);
scanf("%d%d", &S, &T);
graph.n = (K + 1) * n; // Split points
graph.s = S * (K + 1); // Full packs.
for (int i = 1; i <= m; i++) {
lli a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
for (int j = K; j >= 1; j--)
graph.addedge((a - 1) * (K + 1) + j + 1, (b - 1) * (K + 1) + j, c);
}
graph.eval();
// Evaluated results, retrieving.
lli res = infinit;
for (int i = 1; i <= K + 1; i++)
res = min(res, graph.dist[(T - 1) * (K + 1) + i]);
printf("%lld\n", res);
return 0;
}Source Code
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXN 10002
using namespace std;
int n,m,K,S,T,zz,head[MAXN];
struct bian{int to,nx,v;} e[MAXN*10];
struct dui{int w,c;} q[MAXN*10];
int dis[MAXN][12],pd[MAXN][12],ans;
void insert(int x,int y,int z)
{
zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=z; e[zz].nx=head[y]; head[y]=zz;
}
void init()
{
scanf("%d%d%d",&n,&m,&K);
scanf("%d%d",&S,&T);
int i,x,y,z;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
}
}
void spfa()
{
int t=0,w=1,i,x,ct,p;
memset(dis,127,sizeof(dis));
q[0].w=S; q[0].c=0; dis[S][0]=0; pd[S][0]=1;
while(t!=w)
{x=q[t].w; ct=q[t].c; t=(t+1)%100000;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p][ct]>dis[x][ct]+e[i].v)
{dis[p][ct]=dis[x][ct]+e[i].v;
if(!pd[p][ct])
{if(dis[p][ct]<dis[q[t].w][q[t].c])
{t=(t+100000-1)%100000;
q[t].w=p; q[t].c=ct; pd[p][ct]=1;
}
else
{q[w].w=p; q[w].c=ct; pd[p][ct]=1; w=(w+1)%100000;}
}
}
if(ct+1<=K&&dis[p][ct+1]>dis[x][ct])
{dis[p][ct+1]=dis[x][ct];
if(!pd[p][ct+1])
{if(dis[p][ct+1]<dis[q[t].w][q[t].c])
{t=(t+100000-1)%100000;
q[t].w=p; q[t].c=ct+1; pd[p][ct+1]=1;
}
else
{q[w].w=p; q[w].c=ct+1; pd[p][ct+1]=1; w=(w+1)%100000;}
}
}
}
pd[x][ct]=0;
}
ans=1<<30;
for(i=0;i<=K;i++)
ans=min(ans,dis[T][i]);
printf("%d\n",ans);
}
int main()
{
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
init(); spfa();
return 0;
}