1905.Travel in Time

http://acm.timus.ru/problem.aspx?space=1&num=1905
ある星のある時間を一つの点として図を作ります.時間は待つことができますので、同じ星の隣の時間も加算されます.
最後はdfs bfsでいいです.最初はずっとTLEです.  元々はvectorが役に立たなかったです.  パスを記録する時、ずっと0の位置で結果を挿入するのは複雑度が高すぎます.
最後の席にします.バックでいいです
bfsコード:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

#define sint short int

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N=300005;

const LL K=10000000;

const int INF=0x3f3f3f3f;

//typedef pair<int,int>point;

struct node

{

    int j,next;

}side[N];

int head[N],I;

bool visited[N];

int f[N];

int sf[N];

struct node1

{

    int k;

    LL x;

}mem[N];

map<LL,int>mt;

vector<int>vt;

void add(int i,int j)

{

    side[I].j=j;

    side[I].next=head[i];

    head[i]=I++;

}

int nd,m;

bool bfs(int s)

{

    queue<int>qt;

    qt.push(s);

    visited[s]=true;

    f[s]=-1;

    sf[s]=-1;

    while(!qt.empty())

    {

        int x=qt.front();qt.pop();

        if(x==nd)

        return true;

        for(int t=head[x];t!=-1;t=side[t].next)

        {

            int j=side[t].j;

            if(!visited[j])

            {

                visited[j]=true;

                qt.push(j);

                f[j]=x;

                sf[j]=t;

            }

        }

    }

    return false;

}

void dfs(int x)

{

    if(f[x]!=-1)

    dfs(f[x]);

    if(sf[x]<=m&&f[x]!=-1)

    vt.push_back(sf[x]);

}

bool cmp(node1 a,node1 b)

{

    return a.x<b.x;

}

int main()

{

    //freopen("data.in","r",stdin);

    int n;

    cin>>n>>m;

    memset(head,-1,sizeof(head));

    I=1;

    int k=1;

    LL p1,p2,t1,t2;

    LL x1,x2;

    for(int i=1;i<=m;++i)

    {

        cin>>p1>>p2>>t1>>t2;

        x1=p1*K+t1;

        x2=p2*K+t2;

        if(mt.find(x1)==mt.end())

        {mem[k].x=x1;mt[x1]=k++;}

        if(mt.find(x2)==mt.end())

        {mem[k].x=x2;mt[x2]=k++;}

        add(mt[x1],mt[x2]);

    }

    cin>>p1>>p2>>t1>>t2;

    x1=p1*K+t1;

    x2=p2*K+t2;

    if(mt.find(x1)==mt.end())

    {mem[k].x=x1;mt[x1]=k++;}

    if(mt.find(x2)==mt.end())

    {mem[k].x=x2;mt[x2]=k++;}

    nd=mt[x2];

    for(int i=1;i<k;++i)

    mem[i].k=i;

    sort(mem+1,mem+k,cmp);

    for(int i=1;i<k-1;++i)

    if(mem[i].x/K==mem[i+1].x/K)

    add(mem[i].k,mem[i+1].k);

    memset(visited,false,sizeof(visited));

    if(bfs(mt[x1]))

    {

        dfs(nd);

        cout<<vt.size()<<endl;

        for(unsigned int i=0;i<vt.size();++i)

        {

            if(i>0)

            cout<<" ";

            cout<<vt[i];

        }

        cout<<endl;

    }else

    {

        cout<<"Impossible"<<endl;

    }

    return 0;

}

dfsコード:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

#define sint short int

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N=300005;

const LL K=10000000;

const int INF=0x3f3f3f3f;

//typedef pair<int,int>point;

struct node

{

    int j,next;

}side[N];

int head[N],I;

bool visited[N];

struct node1

{

    int k;

    LL x;

}mem[N];

map<LL,int>mt;

vector<int>vt;

void add(int i,int j)

{

    side[I].j=j;

    side[I].next=head[i];

    head[i]=I++;

}

int nd,m;

bool dfs(int x)

{

    visited[x]=true;

    if(x==nd)

    return true;

    for(int t=head[x];t!=-1;t=side[t].next)

    {

        int j=side[t].j;

        if(!visited[j])

        {

            if(dfs(j))

            {

                if(t<=m)

                vt.push_back(t);

                return true;

            }

        }

    }

    return false;

}

bool cmp(node1 a,node1 b)

{

    return a.x<b.x;

}

int main()

{

    //freopen("data.in","r",stdin);

    int n;

    cin>>n>>m;

    memset(head,-1,sizeof(head));

    I=1;

    int k=1;

    LL p1,p2,t1,t2;

    LL x1,x2;

    for(int i=1;i<=m;++i)

    {

        cin>>p1>>p2>>t1>>t2;

        x1=p1*K+t1;

        x2=p2*K+t2;

        if(mt.find(x1)==mt.end())

        {mem[k].x=x1;mt[x1]=k++;}

        if(mt.find(x2)==mt.end())

        {mem[k].x=x2;mt[x2]=k++;}

        add(mt[x1],mt[x2]);

    }

    cin>>p1>>p2>>t1>>t2;

    x1=p1*K+t1;

    x2=p2*K+t2;

    if(mt.find(x1)==mt.end())

    {mem[k].x=x1;mt[x1]=k++;}

    if(mt.find(x2)==mt.end())

    {mem[k].x=x2;mt[x2]=k++;}

    nd=mt[x2];

    for(int i=1;i<k;++i)

    mem[i].k=i;

    sort(mem+1,mem+k,cmp);

    for(int i=1;i<k-1;++i)

    if(mem[i].x/K==mem[i+1].x/K)

    add(mem[i].k,mem[i+1].k);

    memset(visited,false,sizeof(visited));

    if(dfs(mt[x1]))

    {

        cout<<vt.size()<<endl;

        for(int i=vt.size()-1;i>=0;--i)

        {



            cout<<vt[i]<<" ";

        }

        cout<<endl;

    }else

    {

        cout<<"Impossible"<<endl;

    }

    return 0;

}