https://loj.ac/problem/10083 题目描述 给出一张图，每条边有两个边权，定义其最小路径为不存在一条路径两种边权都小于它的两种边权，求这张图的最小路径的条数。 思路 首先这道题有两
https://loj.ac/problem/10083
题目描述
给出一张图，每条边有两个边权，定义其最小路径为不存在一条路径两种边权都小于它的两种边权，求这张图的最小路径的条数。
思路
首先这道题有两类边权，我们考虑把一类边权压入dis数组中，即我们用dis[i][j]表示到达i点，花费费用为j时所需要的最少时间。那么假设我们用w1表示i到j的费用，w2表示i到j的时间，那么dis[i][j]=dis[i][j-w1]+w2。这样我们可以直接进行最短路计算，这样已经足以通过这道题。
不过我们考虑优化，如果存在一个f[j][k]<f[i][j]并且k<j，那么这就肯定不是最优解，不用再更新，而对k的维护，我们可以用树状数组维护f[i][0..j]中的最小值，再进行判断即可。结果我们只要遍历f[n][i]，在费用单增情况下时间小即可。
代码
#include <bits/stdc++.h> using namespace std; struct aa { int pos,val; aa(int pos=0,int val=0):pos(pos),val(val) {} }; int nxt[660],to[660],w1[660],w2[660],head[330],tot; int f[330][10005],dis[330][10005],N; bool exist[330][10005]; void add_edge(int x,int y,int v,int tim) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w1[tot]=v; w2[tot]=tim; } int lowbit(int x) { return x&(-x); } void add(int x,int y,int v) { y++; for(;y<=N;y+=lowbit(y))f[x][y]=min(f[x][y],v); } int query(int x,int y) { y++; int ans=0x3f3f3f3f; for(;y;y-=lowbit(y))ans=min(ans,f[x][y]); return ans; } void spfa(int s) { memset(dis,0x3f,sizeof(dis)); memset(f,0x3f,sizeof(f)); queue<aa>q; q.push(aa(s,0));exist[s][0]=1; dis[s][0]=0; add(s,0,0); while(!q.empty()) { aa u=q.front();q.pop(); exist[u.pos][u.val]=0; for(int i=head[u.pos];~i;i=nxt[i]) { int v=to[i],m=u.val+w1[i]; if(query(v,m)>dis[u.pos][u.val]+w2[i]) { dis[v][m]=dis[u.pos][u.val]+w2[i]; add(v,m,dis[v][m]); if(!exist[v][m]) { exist[v][m]=1; q.push(aa(v,m)); } } } } } int main() { int n,m,s,e; memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&e); for(int i=1;i<=m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); add_edge(a,b,c,d);add_edge(b,a,c,d); } N=n*100; spfa(s); int tim=0x3f3f3f3f,ans=0; for(int i=0;i<=N;i++) if(dis[e][i]<tim)ans++,tim=dis[e][i]; printf("%d",ans); return 0; }