CSU

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333

这题多了一个限制条件是每一条路都会规律的开放a时间关闭b时间,车子必须在开放的时候进入,在关闭之前出来,那么在加边的时候只要权值>开放时间的就不用加进去了.

还有一个问题是重边,那么用邻接表存储就好,并且这题不用spfa就超时,至于判断到达某一个点的时间,只要比较dist[x]%(temp.a+temp.b)的数即可.

算出来之后a需要判断是否还能够在剩余时间通过这个路口,不然就需要等待。还有算出需要等待的时间后必须判断是不是能更新目标点,否则会wa.

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <vector>
  5 #include <cstring>
  6 #include <string>
  7 #include <algorithm>
  8 #include <string>
  9 #include <set>
 10 #include <functional>
 11 #include <numeric>
 12 #include <sstream>
 13 #include <stack>
 14 #include <map>
 15 #include <queue>
 16 #include <deque>
 17 //#pragma comment(linker, "/STACK:102400000,102400000")
 18 #define CL(arr, val)    memset(arr, val, sizeof(arr))
 19 
 20 #define ll long long
 21 #define INF 0x7f7f7f7f
 22 #define lc l,m,rt<<1
 23 #define rc m + 1,r,rt<<1|1
 24 #define pi acos(-1.0)
 25 
 26 #define L(x)    (x) << 1
 27 #define R(x)    (x) << 1 | 1
 28 #define MID(l, r)   (l + r) >> 1
 29 #define Min(x, y)   (x) < (y) ? (x) : (y)
 30 #define Max(x, y)   (x) < (y) ? (y) : (x)
 31 #define E(x)        (1 << (x))
 32 #define iabs(x)     (x) < 0 ? -(x) : (x)
 33 #define OUT(x)  printf("%I64d
", x)
 34 #define lowbit(x)   (x)&(-x)
 35 #define Read()  freopen("a.txt", "r", stdin)
 36 #define Write() freopen("b.txt", "w", stdout);
 37 #define maxn 310
 38 #define maxv 50010
 39 #define mod 1000000000
 40 using namespace std;
 41 
 42 struct edge
 43 {
 44     int to,weight,a,b;
 45 };
 46 vector<edge>adjmap[maxv]; //动态邻接表
 47 bool in_queue[maxn]; //顶点是否在队列中
 48 int dist[maxn];//源点到各点的最短路径
 49 int nodesum; //顶点数
 50 int edgesum; //边数
 51 int S,T;//起点和终点
 52 
 53 void SPFA(int source)
 54 {
 55     deque<int>dq;
 56     int i,j,x,to;
 57     for(int i=1;i<=nodesum;i++)
 58     {
 59         in_queue[i]=false;
 60         dist[i]=INF;
 61     }
 62     dq.push_back(source);
 63     dist[source]=0;
 64     in_queue[source]=true;
 65     //初始化 完成
 66     while(!dq.empty())
 67     {
 68         x=dq.front();  //取出队首元素
 69         dq.pop_front();
 70         in_queue[x]=false; //访问标记置0 ,同一个顶点可以访问多次,只要dist值变小
 71         for(i=0;i<adjmap[x].size();i++)
 72         {
 73             to=adjmap[x][i].to;
 74             edge temp=adjmap[x][i];
 75            // cout<<temp.a<<" "<<temp.b<<endl;
 76             if((dist[x]<INF)&&(dist[to]>dist[x]+temp.weight))
 77             {
 78                 int t=dist[x]%(temp.a+temp.b),t1;
 79                 //cout<<dist[x]<<" "<<t<<endl;
 80                 if(t<=temp.a)
 81                 {
 82                     if(temp.a-t-temp.weight>=0) t1=temp.weight;
 83                     else t1=temp.a-t+temp.b+temp.weight;
 84                 }
 85                 else t1=temp.a+temp.b-t+temp.weight;
 86               //  cout<<t1<<endl;
 87                 if(dist[to]>dist[x]+t1) dist[to]=dist[x]+t1;
 88                 else continue;   //注意这里  
 89                 if(!in_queue[to])
 90                 {
 91                     in_queue[to]=true;
 92                     if(!dq.empty())
 93                     {
 94                         if(dist[to]>dist[dq.front()]) dq.push_back(to); //大的加入 队尾
 95                         else dq.push_front(to); //小的加入队首
 96                     }
 97                     else dq.push_back(to); //队列为空加入队尾
 98                 }
 99             }
100         }
101     }
102 }
103 
104 int main()
105 {
106     //Read;
107     int i,s,e,w,x,y,j=1;
108     edge temp;
109     while(cin>>nodesum>>edgesum>>S>>T)
110     {
111         for(int i=1;i<=nodesum;i++) adjmap[i].clear();
112         for(int i=1;i<=edgesum;i++)
113         {
114             cin>>s>>e>>x>>y>>w;
115             if(w<=x)
116             {
117                 temp.to=e;
118                 temp.weight=w;
119                 temp.a=x,temp.b=y;
120                 adjmap[s].push_back(temp);
121             }
122         }
123         SPFA(S);
124         cout<<"Case "<<j++<<":"<<" "<<dist[T]<<endl;
125     }
126     return 0;
127 }