今天被loli的板子模拟赛AprilFool了一波…非常难受…于是…

水题愉♂悦身心

卑怯的人,即使有万丈的怒火,除弱草以外,又能烧掉什么呢? ——鲁迅

[BeiJing wc2012]冻结

我居然也忘了priority_queuecmp是反着的…好久没写最短路了…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (500000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFF)
#define MAXK (50)
#define bh(x, i) (((i) * MAXK) + x)
#define pii pair<int, int>
int dis[MAXN];
using namespace std;
struct edg
{
    int from, to, next, cost;
}b[MAXM << 1];
struct cmp
{
    bool operator () (const pii x, const pii y)
    {
        return x.second > y.second;
    }
};
int g[MAXN], cntb, n, m, k;
void dijk()
{
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(bh(1, 0), 0));
    dis[1] = 0;
    while (!q.empty())
    {
        pii dq = q.top();
        q.pop();
        if (vis[dq.first])
            continue;
        vis[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
            if (dis[b[i].to] > dis[dq.first] + b[i].cost)
            {
                dis[b[i].to] = dis[dq.first] + b[i].cost;
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
    }
}
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
    {
        int srx, sry, srz;
        scanf("%d%d%d", &srx, &sry, &srz);
        for (int j = 0; j <= k; j++)
        {
            adn(bh(srx, j), bh(sry, j), srz);
            adn(bh(sry, j), bh(srx, j), srz);
            if (j != k)
            {
                adn(bh(srx, j), bh(sry, j + 1), srz >> 1);
                adn(bh(sry, j), bh(srx, j + 1), srz >> 1);
            }
        }
    }
    dijk();
    int ans = INF;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[bh(n, i)]);
    printf("%d", ans);
    return 0;
}

/*
4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
*/

[JLOI2011]飞行路线

注意这个题数据毒啊…把MAXN开大点才行啊…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0X7FFFFFF)
#define MAXN (1000000 + 5)
#define MAXM (5000000 + 5)
#define MAXK (10000)
#define bh(x, i) (MAXK * (i) + x)
#define pii pair<int, int>
using namespace std;
int s, t;
struct cmp
{
    bool operator () (const pii x, const pii y)
    {
        return x.second > y.second;
    }
};
struct edg
{
    int from, to, next, cost;
}b[MAXM];
int g[MAXN], cntb, n, m, k, dis[MAXN];
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void dijk()
{
    bool vis[MAXN];
    memset(dis, 0x7f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(bh(s, 0), 0));
    dis[bh(s, 0)] = 0;
    while (!q.empty())
    {
        pii dq = q.top();
        q.pop();
        if (vis[dq.first])
            continue;
        vis[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
            if (dis[b[i].to] > dis[dq.first] + b[i].cost)
            {
                dis[b[i].to] = dis[dq.first] + b[i].cost;
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    scanf("%d%d", &s, &t);
    ++s, ++t;
    for (int i = 1; i <= m; i++)
    {
        int srx, sry, srz;
        scanf("%d%d%d", &srx, &sry, &srz);
        ++srx, ++sry;
        for (int j = 0; j <= k; j++)
        {
            adn(bh(srx, j), bh(sry, j), srz);
            adn(bh(sry, j), bh(srx, j), srz);
            if (j != k)
            {
                adn(bh(srx, j), bh(sry, j + 1), 0);
                adn(bh(sry, j), bh(srx, j + 1), 0);
            }
        }
    }
    dijk();
    int ans = INF;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[bh(t, i)]);
    printf("%d", ans);
    return 0;
}

/*
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
*/

By 怯懦的 Cansult