双调路径
题目描述
题目大意
在一张无向图中，我们给出一些边，这一条边有我们对应需要的通过这条边的时间和花费，从A点到B点可能有N多种方式到达，对于每种方式当我们的花费和时间都比其中一种方式大时，此种方式不是最短路，但是如果一种方式花费小而时间大，一种方式时间大而花费小，这样我们无法比较，两种方式都暂时属于我们的最短路。
题目分析
本题的题目要求求出从 s 到 e 的最小路径条数
在我们理解了题意之后，应该是很容易就能想出双限制的最短路做法（把我们的dis值用一个二维数组来表示）
普通最短路就是距离限制，我们通过 dis[x] 表示到达点 x 的最小距离
本题最短路则是限制距离（时间）和花费，那我们就加一维使其变成二维数组，那么我们的dis就会有两个值来控制。
—— 用 dis[x][y] 表示到达点 x 花费 y 块钱的最小距离（时间）
最后枚举花费 i ，然后找到满足最短路径的点 dis[e][i]，有多少这样的点我们就可以用一个累加器ans来累计答案，最后输出就行了
怎么判断是否是满足最短路径的点？
设一个变量 last（我用的是last，自己可以随便定义） == 0x3f3f3f3f（极大值就可以） ，如果当前的 dis[e][i] <ans ，则是满足我们条件的点（ ans 表示的是时间）
代码
#include <bits/stdc++.h>//万能头文件
using namespace std;
int n,m,st,ed;
struct edge{结构体
int v;
int w;
int t;
};
vector<edge> e[105];//结构体数组e中有 i v w t四个数表示从i点到v点的距离为w，时间为t
int d[105][100005];//这个d数组第一维是表示第几种方式第二维表示时间值表示金钱（花费）
bool vis[105];//记录是否重复判断
int main() {
memset(vis,0,sizeof(vis));
memset(d,127,sizeof(d));//“127”代表的是一个极大的值
cin>>n>>m>>st>>ed;
for(int i=1;i<=m;i++){
int u,v,w,t;
cin>>u>>v>>w>>t;
e[u].push_back((edge){v,w,t});
e[v].push_back((edge){u,w,t});
}//预处理
queue<int> q;
q.push(st);
vis[st]=1;
for(int i=1;i<=10000;i++)d[st][i]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].v,w=e[u][i].w,t=e[u][i].t;
bool flag=0;
for(int j=0;j<=10000-w;j++){
if(d[v][j+w]>d[u][j]+t){
d[v][j+w]=d[u][j]+t;
flag=1;
}
}
if(flag){
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}//spfa的模板
int ans=0,last=99999999;
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=15;j++){
cout<<d[i][j]<<' ';
}
cout<<endl;
}
*/ //当时调试用的，不影响
for(int i=0;i<=10000;i++){
if(d[ed][i]>=last)continue;
last=d[ed][i];
ans++;//ans累加，输出答案
}
cout<<ans;
return 0;//结束程序
}