题意：有n（1<=n<=100）块水平不相交木板，一堆小鼠每个tmin从洞口出来，如果不碰到不动的小鼠（一直不动）会沿着原来的方向一直走，初始方向向右。
问最后最多有多少小鼠能够到达目的点和最后一个小鼠的到达时间。
题解：简单的Dijkstra最短路被我写的好丑，维护每个模板下方模板的编号，由于n小可以暴力。
Sure原创，转载请注明出处
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <queue>
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
using namespace std;
const int inf = 1 << 29;
const int maxn = 110;
struct BB
{
int x1,x2,y;
int l,r;
bool operator < (const BB &other) const
{
if(y == other.y) return x1 < other.x1;
return y > other.y;
}
}seg[maxn];
struct ddd
{
int cost,val;
int x,v,dir,up;
bool operator < (const ddd &other) const
{
if(cost == other.cost) return val > other.val;
return cost > other.cost;
}
};
priority_queue <ddd> Q;
bool vis[maxn][2];
int dis[maxn][2][2];
int m,n,t,top;
int sx,sy,ex,ey,fin;
void read()
{
memset(vis,false,sizeof(vis));
scanf("%d %d %d %d %d",&sx,&sy,&ex,&ey,&m);
top = 1;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&seg[top].x1,&seg[top].x2,&seg[top].y);
if(seg[top].y <= sy && seg[top].y >= ey)
{
top++;
}
}
sort(seg + 1 , seg + top);
return;
}
bool make()
{
fin = -1;
for(int i=1;i<top;i++)
{
if(seg[i].y == ey && seg[i].x1 <= ex && seg[i].x2 >= ex)
{
fin = i;
break;
}
}
if(fin == -1 || sy < ey) return false;
while(!Q.empty()) Q.pop();
ddd tmp;
for(int i=1;i<top;i++)
{
if(seg[i].y <= sy && seg[i].x1 <= sx && seg[i].x2 >= sx)
{
tmp.cost = 0;
tmp.dir = 1;
tmp.v = i;
tmp.x = sx;
tmp.val = 0;
tmp.up = 0;
Q.push(tmp);
if(fin == i) return true;
break;
}
}
for(int i=1;i<top;i++)
{
seg[i].l = seg[i].r = -1;
for(int j=i+1;j<top;j++)
{
if(seg[i].l == -1 && seg[j].x1 <= seg[i].x1 && seg[j].x2 >= seg[i].x1)
{
seg[i].l = j;
}
if(seg[i].r == -1 && seg[j].x1 <= seg[i].x2 && seg[j].x2 >= seg[i].x2)
{
seg[i].r = j;
}
if(seg[i].l != -1 && seg[i].r != -1) break;
}
dis[i][0][0] = dis[i][0][1] = dis[i][1][0] = dis[i][1][1] = inf;
}
return true;
}
inline bool relax(int x,int y,int a,int b)
{
if(a < x || (a == x && b < y)) return true;
return false;
}
void bfs(bool flag)
{
if(flag == false)
{
puts("0 0");
return;
}
int num = inf,sum = inf;
ddd cur,tmp;
while(!Q.empty())
{
cur = Q.top();
Q.pop();
if(cur.v == fin && cur.x == ex)
{
num = cur.cost;
sum = cur.val;
break;
}
int pos = cur.up < 0 ? 0 : 1;
if(vis[ABS(cur.up)][pos]) continue;
vis[ABS(cur.up)][pos] = true;
if(cur.v == fin)
{
if(cur.x < ex)
{
if(cur.dir == 1)
{
if(relax(num , sum , cur.cost , cur.val + ex - cur.x))
{
num = cur.cost;
sum = cur.val + ex - cur.x;
}
}
else if(cur.cost < n-1)
{
if(relax(num , sum , cur.cost + 1 , cur.val + ex - cur.x))
{
num = cur.cost + 1;
sum = cur.val + ex - cur.x;
}
}
}
else
{
if(cur.dir == -1)
{
if(relax(num , sum , cur.cost , cur.val - ex + cur.x))
{
num = cur.cost;
sum = cur.val - ex + cur.x;
}
}
else if(cur.cost < n-1)
{
if(relax(num , sum , cur.cost + 1 , cur.val - ex + cur.x))
{
num = cur.cost + 1;
sum = cur.val - ex + cur.x;
}
}
}
}
else if(cur.dir == 1)
{
tmp = cur;
tmp.v = seg[cur.v].r;
tmp.val += seg[cur.v].x2 - cur.x;
tmp.x = seg[cur.v].x2;
tmp.up = cur.v;
if(tmp.v != -1 && vis[cur.v][1] == false && relax(dis[cur.v][1][0] , dis[cur.v][1][1] , tmp.cost , tmp.val))
{
dis[cur.v][1][0] = tmp.cost;
dis[cur.v][1][1] = tmp.val;
Q.push(tmp);
}
if(cur.cost < n-1)
{
tmp = cur;
tmp.cost++;
tmp.dir = -1;
tmp.v = seg[cur.v].l;
tmp.val += cur.x - seg[cur.v].x1;
tmp.x = seg[cur.v].x1;
tmp.up = -cur.v;
if(tmp.v != -1 && vis[cur.v][0] == false && relax(dis[cur.v][0][0] , dis[cur.v][0][1] , tmp.cost , tmp.val))
{
dis[cur.v][0][0] = tmp.cost;
dis[cur.v][0][1] = tmp.val;
Q.push(tmp);
}
}
}
else
{
tmp = cur;
tmp.v = seg[cur.v].l;
tmp.val += cur.x - seg[cur.v].x1;
tmp.x = seg[cur.v].x1;
tmp.up = -cur.v;
if(tmp.v != -1 && vis[cur.v][0] == false && relax(dis[cur.v][0][0] , dis[cur.v][0][1] , tmp.cost , tmp.val))
{
dis[cur.v][0][0] = tmp.cost;
dis[cur.v][0][1] = tmp.val;
Q.push(tmp);
}
if(cur.cost < n-1)
{
tmp = cur;
tmp.cost++;
tmp.dir = 1;
tmp.v = seg[cur.v].r;
tmp.val += seg[cur.v].x2 - cur.x;
tmp.x = seg[cur.v].x2;
tmp.up = cur.v;
if(tmp.v != -1 && vis[cur.v][1] == false && relax(dis[cur.v][1][0] , dis[cur.v][1][1] , tmp.cost , tmp.val))
{
dis[cur.v][1][0] = tmp.cost;
dis[cur.v][1][1] = tmp.val;
Q.push(tmp);
}
}
}
}
if(sum < inf) printf("%d %d\n",n - num , (n-1) * t + sum + sy - ey);
else puts("0 0");
return;
}
int main()
{
while(~scanf("%d %d",&n,&t))
{
read();
bfs(make());
}
return 0;
}