行动! 行动! (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;
}