Source Code

Problem: 1158  User: yzhw 
Memory: 540K  Time: 485MS 
Language: C++  Result: Accepted 

Source Code 
# include <iostream>
# include <cmath>
# include <queue>
# include <vector>
using namespace std;
struct
{
    int a,l1,l2,l3,l4;
}data[301];
struct node
{
   int t,len;
};
vector<node> graph[301];
int isin(int t,int pos)
{
    int x=(t-data[pos].l1)/data[pos].a;
    return t>=data[pos].a*x+data[pos].l1&&t<data[pos].a*x+data[pos].l2;
}
int up(double num)
{
    return fabs(num-(int)(num))<1e-4?(int)(num-1):(int)(num);
}
int down(double num)
{
    return fabs(num-(int)(num))<1e-4?(int)(num):(int)(num+1);
}
int next(int t,int pos1,int pos2)
{
    int res=99999999;
    if(isin(t,pos1)==isin(t,pos2)) return t;
    if(isin(t,pos1))
    {
       if(data[pos1].a*((t-data[pos1].l1)/data[pos1].a)+data[pos1].l2!=data[pos2].a*((t-data[pos2].l3)/data[pos2].a)+data[pos2].l4)
       {
         if(down((t-data[pos2].l1)/(double)(data[pos2].a))<=up(((int)((t-data[pos1].l1)/data[pos1].a)*data[pos1].a+data[pos1].l2-data[pos2].l1)/(double)(data[pos2].a)))
             res=min(res,data[pos2].a*down((t-data[pos2].l1)/(double)(data[pos2].a))+data[pos2].l1);
         if(down((t-data[pos1].l3)/(double)(data[pos1].a))<=up(((int)((t-data[pos2].l3)/data[pos2].a)*data[pos2].a+data[pos2].l4-data[pos1].l3)/(double)(data[pos1].a)))
             res=min(res,data[pos1].a*down((t-data[pos1].l3)/(double)(data[pos1].a))+data[pos1].l3);
       }
       else
       {
           t=data[pos1].a*((t-data[pos1].l1)/data[pos1].a)+data[pos1].l2;
           if(down((t-data[pos2].l3)/(double)(data[pos2].a))<=up(((int)((t-data[pos1].l3)/data[pos1].a)*data[pos1].a+data[pos1].l4-data[pos2].l3)/(double)(data[pos2].a)))
             res=min(res,data[pos2].a*down((t-data[pos2].l3)/(double)(data[pos2].a))+data[pos2].l3);
           if(down((t-data[pos1].l1)/(double)(data[pos1].a))<=up(((int)((t-data[pos2].l1)/data[pos2].a)*data[pos2].a+data[pos2].l2-data[pos1].l1)/(double)(data[pos1].a)))
             res=min(res,data[pos1].a*down((t-data[pos1].l1)/(double)(data[pos1].a))+data[pos1].l1);
       }
    }
    else
    {
       if(data[pos1].a*((t-data[pos1].l3)/data[pos1].a)+data[pos1].l4!=data[pos2].a*((t-data[pos2].l1)/data[pos2].a)+data[pos2].l2)
       {
        if(down((t-data[pos2].l3)/(double)(data[pos2].a))<=up(((int)((t-data[pos1].l3)/data[pos1].a)*data[pos1].a+data[pos1].l4-data[pos2].l3)/(double)(data[pos2].a)))
             res=min(res,data[pos2].a*down((t-data[pos2].l3)/(double)(data[pos2].a))+data[pos2].l3);
         if(down((t-data[pos1].l1)/(double)(data[pos1].a))<=up(((int)((t-data[pos2].l1)/data[pos2].a)*data[pos2].a+data[pos2].l2-data[pos1].l1)/(double)(data[pos1].a)))
             res=min(res,data[pos1].a*down((t-data[pos1].l1)/(double)(data[pos1].a))+data[pos1].l1);
       }
       else
       {
           t=data[pos1].a*((t-data[pos1].l3)/data[pos1].a)+data[pos1].l4;
           if(down((t-data[pos2].l1)/(double)(data[pos2].a))<=up(((int)((t-data[pos1].l1)/data[pos1].a)*data[pos1].a+data[pos1].l2-data[pos2].l1)/(double)(data[pos2].a)))
             res=min(res,data[pos2].a*down((t-data[pos2].l1)/(double)(data[pos2].a))+data[pos2].l1);
           if(down((t-data[pos1].l3)/(double)(data[pos1].a))<=up(((int)((t-data[pos2].l3)/data[pos2].a)*data[pos2].a+data[pos2].l4-data[pos1].l3)/(double)(data[pos1].a)))
             res=min(res,data[pos1].a*down((t-data[pos1].l3)/(double)(data[pos1].a))+data[pos1].l3);
       }
    }
    return res==99999999?-1:res;
}
int main()
{
    int s,t,n,m;
    cin>>s>>t>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char t1;
        int t2,t3,t4;
        cin>>t1>>t2>>t3>>t4;
        data[i].a=t3+t4;
        if(t1=='B')
        {
           data[i].l1=-(t3-t2);
           data[i].l2=t2;
           data[i].l3=data[i].l2;
           data[i].l4=data[i].l3+t4;
        }
        else
        {
           data[i].l3=-(t4-t2);
           data[i].l4=t2;
           data[i].l1=data[i].l4;
           data[i].l2=data[i].l1+t3;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int t1,t2;
        node tmp;
        cin>>t1>>t2>>tmp.len;
        tmp.t=t1;
        graph[t2].push_back(tmp);
        tmp.t=t2;
        graph[t1].push_back(tmp);
        
    }
    queue<int> q;
    int len[301];
    bool inqueue[301];
    for(int i=1;i<=n;i++)
      len[i]=99999999,inqueue[i]=0;
    inqueue[s]=1;
    len[s]=0;
    q.push(s);
  //  next(96,28,47);
    while(!q.empty())
    {
       int pos=q.front();
       q.pop();
       inqueue[pos]=0;
       for(int i=0;i<graph[pos].size();i++)
       {
          int nexttime=next(len[pos],pos,graph[pos][i].t);
          if(nexttime!=-1&&nexttime+graph[pos][i].len<len[graph[pos][i].t])
          {
             len[graph[pos][i].t]=nexttime+graph[pos][i].len;
          
             if(!inqueue[graph[pos][i].t])
             {
                inqueue[graph[pos][i].t]=1;
                q.push(graph[pos][i].t);
             }
          }
       }   
    }
    if(len[t]==99999999) cout<<0<<endl;
    else cout<<len[t]<<endl;
   // system("pause");
    return 0;
}

• Re:贴AC代码，SPFA过的~ (75) yzhw 2010-05-29 01:54:11
• 膜拜~~~ (0) lanseniao 2010-08-06 21:23:16
• 很OOP的代碼 (4365) miklcct 2011-08-03 14:10:07