HDU 5669 Road

问题描述

\ \ \ \    TA想要让别人把他叫做Taishenle [Au]gust.

\ \ \ \    因为他厉害到能上天,所以喜欢在天上飞,让自己与风融为一体,但是长时间的飞行会很累,通常他还是会选择走路.

\ \ \ \    现在有nn个地点,其中某些地点之间有道路相连.有mm个道路信息,每个道路信息用(a,b,c,d,w)(a,b,c,d,w)表示,意为对任意两个地点xx,yy,满足a\le x\le ba≤x≤b,c\le y\le dc≤y≤d,则在xx,yy两地之间修一条道路,走过这条道路消耗的时间为ww.Taishenle [Au]gust会从11号地点出发,想要到nn号地点,但是Taishenle [Au]gust每天可以做kk次飞行,每次飞行可以使得他瞬间通过某条已有的路径,从某个点抵达另一个点.

\ \ \ \    现在Taishenle [Au]gust想要知道他从11号点到nn号点消耗的最少时间.      

输入描述

\ \ \ \    第一行一个数T,为测试数据组数(出于某些原因,此题T=1).

\ \ \ \    第二行三个数nn,mm,kk.

\ \ \ \    接下来,每行五个数aa,bb,cc,dd,ww,意义见题目描述.

\ \ \ \ T=1,1\le n\le 5*10^4    T=1,1≤n≤5∗104,1\le m\le 10^41≤m≤104,0 \le k\le 100≤k≤10,1\le w\le 10^31≤w≤103.      

输出描述

\ \ \ \    一行一个数,为最小时间消耗.

\ \ \ \    如果1号点和n号点不连通,输出"CreationAugust is a sb!".      

输入样例

1
5 3 0
1 2 4 5 42
5 5 4 4 468
1 1 3 3 335      

输出样例

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
const int N = 3e6+ 10;
const int INF = 0x7FFFFFFF;
int T, n, m, t, bg, ed;
int a, b, c, d, e, cnt;
int ft[N], nt[N], u[N], v[N], sz;
int f[N / 3][2], dp[N / 3][11];

void AddEdge(int x, int y, int z)
{
  u[sz] = y; v[sz] = z; nt[sz] = ft[x]; ft[x] = sz++;
}

void build(int x, int l, int r)
{
  f[x][0] = cnt++; f[x][1] = cnt++;
  if (l == r)
  {
    if (l == 1) bg = f[x][0];
    if (l == n) ed = f[x][1];
    AddEdge(f[x][1], f[x][0], 0);
    return;
  }
  int mid = l + r >> 1;
  build(lson); build(rson);
  AddEdge(f[x << 1][0], f[x][0], 0);
  AddEdge(f[x][1], f[x << 1][1], 0);
  AddEdge(f[x << 1 | 1][0], f[x][0], 0);
  AddEdge(f[x][1], f[x << 1 | 1][1], 0);
}

void find(int x, int l, int r, int ll, int rr, int u, int o)
{
  if (ll <= l && r <= rr)
  {
    AddEdge(f[x][0], cnt, 0);
    AddEdge(cnt + o, f[x][1], u);
  }
  else
  {
    int mid = l + r >> 1;
    if (ll <= mid) find(lson, ll, rr, u, o);
    if (rr > mid) find(rson, ll, rr, u, o);
  }
}

struct point
{
  int x, y, z;
  point(int x = 0, int y = 0, int z = 0) :x(x), y(y), z(z) {}
  bool operator<(const point &a)const { return z > a.z; }
};

void dijkstra()
{
  rep(i, 0, cnt) ms(dp[i], -1);
  priority_queue<point> p;
  p.push(point(bg, 0, dp[bg][0] = 0));
  int ans = INF;
  while (!p.empty())
  {
    point q = p.top(); p.pop();
    if (q.x == ed) ans = min(ans, q.z);
    loop(i, ft[q.x], nt)
    {
      if (dp[u[i]][q.y] == -1 || dp[u[i]][q.y] > q.z + v[i])
      {
        p.push(point(u[i], q.y, dp[u[i]][q.y] = q.z + v[i]));
      }
      if (q.y < t&&dp[u[i]][q.y + 1] == -1 || dp[u[i]][q.y + 1] > q.z)
      {
        p.push(point(u[i], q.y + 1, dp[u[i]][q.y + 1] = q.z));
      }
    }
  }
  if (ans == INF) printf("CreationAugust is a sb!\n");
  else printf("%d\n", ans);
}

int main()
{
  inone(T);
  while (T--)
  {
    ms(ft, -1);
    inthr(n, m, t);
    cnt = sz = 0;
    build(1, 1, n);
    rep(i, 1, m) 
    {
      intwo(a, b); inthr(c, d, e);
      find(1, 1, n, a, b, e, 1); cnt++;
      find(1, 1, n, c, d, e, -1); cnt++;
    }
    dijkstra();
  }
  return 0;
}