[BalticOI2002]Bicriterial routing

OJ题号：
　　BZOJ1375、ECNU1468

题目大意：
　　给定一个无向连通图，每条边有两个权值w1和w2。定义一条路径是优秀的当且仅当没有别的路径满足两个权值的和都比该路径小，求s到t的优秀路径条数。

思路：
　　将其中一个权值转化为最短路的一个维度，也就是求出对于同一个结点的不同的w1的和，最小的w2和。
　　然后直接跑Dijkstra就可以了。

#include<cstdio>
#include<cctype>
#include<vector>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int inf=0x7fffffff;
const int V=101,W=101;
struct Edge {
    int to,w1,w2;
};
std::vector<Edge> e[V];
inline void add_edge(const int &u,const int &v,const int &w1,const int &w2) {
    e[u].push_back((Edge){v,w1,w2});
}
int n,m,s,t;
struct Vertex {
    int dis,id,w;
    bool operator > (const Vertex &another) const {
        return dis>another.dis;
    }
};
int d[V][(V-1)*W];
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex>> q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex>>::point_iterator p[V][V*W];
inline void dijkstra() {
    for(register int i=1;i<=n;i++) {
        for(register int j=0;j<(n-1)*W;j++) {
            p[i][j]=q.push((Vertex){d[i][j]=(i==s&&j==0)?0:inf,i,j});
        }
    }
    while(q.top().dis!=inf) {
        const Vertex x=q.top();
        for(register unsigned i=0;i<e[x.id].size();i++) {
            const Edge &y=e[x.id][i];
            if((x.w+y.w1)<(n-1)*W&&(x.dis+y.w2)<d[y.to][x.w+y.w1]) {
                q.modify(p[y.to][x.w+y.w1],(Vertex){d[y.to][x.w+y.w1]=x.dis+y.w2,y.to,x.w+y.w1});
            }
        }
        q.modify(p[x.id][x.w],(Vertex){inf,x.id,x.w});
    }
    q.clear();
}
int main() {
    n=getint(),m=getint(),s=getint(),t=getint();
    for(register int i=1;i<=m;i++) {
        int u=getint(),v=getint(),t=getint(),c=getint();
        add_edge(u,v,t,c);
        add_edge(v,u,t,c);
    }
    dijkstra();
    int ans=0,min=inf;
    for(register int i=0;i<(n-1)*W;i++) {
        if(d[t][i]==inf) continue;
        if(d[t][i]<min) {
            ans++;
            min=d[t][i];
        }
    }
    printf("%d
",ans);
    return 0;
}