UVA12661 有趣的赛车比赛

白书上的例题，n个点m条单向边，每条边周期性开放和关闭，时间分别为a，b
求s到t的最短路

首先对于a>cost的边，可以直接删掉
spfa，算dist的时候，加入等待的时间
然后，就没有然后了

写代码越来越模块化（chou）了

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100007;
const int INF=0x3f3f3f3f;
struct SPFA{
    struct Edge{
        int from,to,cost,a,b;
        Edge(){}
        Edge(int x,int y,int z,int a,int b):
            from(x),to(y),cost(z),a(a),b(b){}
        bool canPass(){return a>=cost;}//题目里的
        void read(){scanf("%d%d%d%d%d",&from,&to,&a,&b,&cost);}
    };
    int n, m;
    vector <Edge> edges;
    vector <int > G[N];

    inline void AddEdge(){
        Edge e; e.read();
        if (!e.canPass())return ;
        edges.push_back(e);
        int top = edges.size();
        G[e.from].push_back(top-1);
    }

    inline void Init(int n,int m){
        this -> n = n; this -> m = m;
        edges.clear();
        for (int i=0;i<=n;i++)G[i].clear();
        for (int i=1;i<=m;i++) AddEdge();
    }

    bool inq[N];
    int d[N],cnt[N];
    inline int spfa(int s,int t){
        queue<int> Q;
        memset(inq, 0, sizeof(inq));
        memset(cnt, 0, sizeof(cnt));
        memset( d ,INF,sizeof( d ));
        d[s] = 0;inq[s]=1;Q.push(s);
        for (;!Q.empty();){
            int u = Q.front();Q.pop();
            inq[u]= 0;
            for (int i=0;i<G[u].size();i++){
                Edge &e = edges[G[u][i]];
                int val = d[u],s = d[u] ;//
                val %= (e.a + e.b);//特殊题目
                if (val>e.a) s+=e.b-(val-e.a);//
                else if (e.a<val+e.cost)s+=e.a+e.b-val;//
                if (d[u]<INF&&s+e.cost<d[e.to]){
                    d[e.to] = s + e.cost;
                    if (!inq[e.to]){
                        Q.push(e.to);inq[e.to] = 1;
                        if (++cnt[e.to]>n)return INF;
                    }
                }
            }
        }
        return d[t];
    }
}g;

int main(){
    //freopen("in.txt","r",stdin);
    int n,m,s,t;
    for (int T=0;~scanf("%d%d%d%d",&n,&m,&s,&t);){
        g.Init(n,m,s,t);
        int ans = g.spfa(s,t);
        printf("Case %d: %d
",++T,ans);
    }
    return 0;
}

这波图论挂vjudge上了
http://vjudge.net/contest/107921#overview
密码cww