或者说..

是这题:http://codeforces.com/gym/100959/attachments/download/4248/20152016-petrozavodsk-winter-training-camp-makoto-rng58-soejima-sontest-4-en.pdf

翻译:

感谢@FizzyDavid 杨主力翻译 以及 在现场怒A这题帮我们提高了排名

给你n个机器人,每个机器人有它的行动方向

一开始1号机器人被触发,如果某个机器人被撞到,那么它将被触发

如果某个机器人被触发,会按照它的行动方向永远的走下去

问:T秒后,每个机器人在哪里

做法:

每个点到由离它最近的并且会撞到它的机器人向它连边,权值为之间的时间差

dijkstra一发即可,注意long long

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
int dire[maxn],x[maxn],y[maxn];
int get_code(char x)
{
    if (x=='L') return 0;
    if (x=='R') return 1;
    if (x=='D') return 2;
    if (x=='U') return 3;
    return -1;
}
map<int,int> ma1;
map<int,int> ma2;
vector<pair<int,int> > xx[100005];
vector<pair<int,int> > yy[100005];
int l[100005],r[100005],u[100005],d[100005];
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * new_edge()
{
    static edge a[800005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
void insert_edge(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
long long dist[100005];
bool visit[100005];
void dijkstra(int s)
{
    priority_queue<pair<long long,int> > q;
    memset(dist,-1,sizeof(dist));
    memset(visit,false,sizeof(visit));
    static int que[maxn];
    q.push(make_pair(0ll,0));
    dist[s]=0;
    que[0]=s;
    for (;!q.empty();)
    {
        int now=q.top().second;
        q.pop();
        edge * t;
        if (visit[now]) continue;
        for (t=li[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[now]+t->weight))
            {
                dist[t->y]=dist[now]+t->weight;
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    long long t;
    ios::sync_with_stdio(false);
    cin>>n>>t;
    int i;
    int sum1=0;
    int sum2=0;
    for (i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
        if (ma1.find(x[i])==ma1.end()) ma1[x[i]]=sum1++;
        if (ma2.find(y[i])==ma2.end()) ma2[y[i]]=sum2++;
        xx[ma1[x[i]]].push_back(make_pair(y[i],i));
        yy[ma2[y[i]]].push_back(make_pair(x[i],i));
        char oper;
        cin>>oper;
        dire[i]=get_code(oper);
    }
    for (i=0;i<sum1;i++)
    {
        sort(xx[i].begin(),xx[i].end());
    }
    for (i=0;i<sum2;i++)
    {
        sort(yy[i].begin(),yy[i].end());
    }
    for (i=0;i<sum1;i++)
    {
        int j;
        for (j=0;j<(int)xx[i].size();j++)
        {
            int t1=xx[i][j].first;
            int t2=xx[i][j].second;
            if (j==0)
            {
                l[t2]=-1;
            }
            else
            {
                l[t2]=l[xx[i][j-1].second];
            }
            if (l[t2]!=-1) insert_edge(l[t2],t2,t1-y[l[t2]]);
            if (dire[t2]==3)
            {
                l[t2]=t2;
            }
        }
        for (j--;j>=0;j--)
        {
            int t1=xx[i][j].first;
            int t2=xx[i][j].second;
            if (j==(int)xx[i].size()-1)
            {
                r[t2]=-1;
            }
            else
            {
                r[t2]=r[xx[i][j+1].second];
            }
            if (r[t2]!=-1) insert_edge(r[t2],t2,y[r[t2]]-t1);
            if (dire[t2]==2)
            {
                r[t2]=t2;
            }
        }
    }
    for (i=0;i<sum2;i++)
    {
        int j;
        for (j=0;j<(int)yy[i].size();j++)
        {
            int t1=yy[i][j].first;
            int t2=yy[i][j].second;
            if (j==0)
            {
                u[t2]=-1;
            }
            else
            {
                u[t2]=u[yy[i][j-1].second];
            }
            if (u[t2]!=-1) insert_edge(u[t2],t2,t1-x[u[t2]]);
            if (dire[t2]==1)
            {
                u[t2]=t2;
            }
        }
        for (j--;j>=0;j--)
        {
            int t1=yy[i][j].first;
            int t2=yy[i][j].second;
            if (j==(int)yy[i].size()-1)
            {
                d[t2]=-1;
            }
            else
            {
                d[t2]=d[yy[i][j+1].second];
            }
            if (d[t2]!=-1) insert_edge(d[t2],t2,x[d[t2]]-t1);
            if (dire[t2]==0)
            {
                d[t2]=t2;
            }
        }
    }
    dijkstra(0);
    for (i=0;i<n;i++)
    {
        if ((dist[i]>=t)||(dist[i]==-1))
        {
            cout<<x[i]<<' '<<y[i]<<'\n';
        }
        else
        {
            long long temp=t-dist[i];
            if (dire[i]==0)
            {
                cout<<x[i]-temp<<' '<<y[i]<<'\n';
            }
            if (dire[i]==1)
            {
                cout<<x[i]+temp<<' '<<y[i]<<'\n';
            }
            if (dire[i]==2)
            {
                cout<<x[i]<<' '<<y[i]-temp<<'\n';
            }
            if (dire[i]==3)
            {
                cout<<x[i]<<' '<<y[i]+temp<<'\n';
            }
        }
    }
    return 0;
}